3 ms·

The Javascript code at Observable has been updated to render it correctly for both even and odd values of n now. This addresses the issues that were pointed ou

The Javascript code at Observable has been updated to render it correctly for both even and odd values of n now. This addresses the issues that were pointed out below for the most part. In short, actually there are some curious patterns in this, and they are not simply equivalent to OEIS A054521 (as we, and others, initially thought they were). For even values of n, they can be rendered by the GCD sequence, without the primality testing. But for odd values the pattern is different and GCD doesn't describe it. The Mathematica code on Github lets you experiment with this. There are some nice versions, and experiments in different ways of coloring or arranging the graph in the Telegram group as well. Telegram group https://t.me/joinchat/G8AnchIna2q8yn1lGHirkA https://t.me/joinchat/G8AnchIna2q8yn1lGHirkA Javascript code https://beta.observablehq.com/@montyxcantsin/unwinding-the-ulam-spiral https://beta.observablehq.com/@montyxcantsin/unwinding-the-u... Mathematica code: https://github.com/shaunxcode/a-pattern-in-the-primes https://github.com/shaunxcode/a-pattern-in-the-primes

airesearcher 8y ago
Also there are versions in Perl and other languages in the Telegram group.
svat 8y ago
One correction (already accepted by your co-author @shaunxcode) is that even for even n, your triangle and the one formed by OEIS A054521 are not equivalent. Specifically, here are some values of N, and (row, column) coordinates where the gcd sequence and your sequence differ: Counterexample: N=14, (R,C) = (13, 3) Counterexample: N=20, (R,C) = (17, 8) Counterexample: N=20, (R,C) = (19, 1) Counterexample: N=30, (R,C) = (17, 7) Counterexample: N=30, (R,C) = (19, 1) Counterexample: N=38, (R,C) = (37, 8) Counterexample: N=44, (R,C) = (31, 2) Counterexample: N=44, (R,C) = (37, 2) Counterexample: N=50, (R,C) = (43, 13) Counterexample: N=74, (R,C) = (73, 43) (For n=74, look at the last shown row in the post right now, for N=73, where there's a “stray” red dot: this dot wouldn't be present in the computed-from-gcd sequence.) There are very few counter-examples though (larger ones seem hard to find); you can see some reasons in my long comment here: https://news.ycombinator.com/item?id=17106193 https://news.ycombinator.com/item?id=17106193 Here's a rough heuristic calculation for how many counterexamples we should expect. Let's say gcd(R,C)=1, so that there should be no “special reason” to expect everything in the set to be composite. Then, as the set contains N numbers each of size roughly (NR^2/2), each is prime with “probability” 1/log(NR^2/2) — this is the Cramer heuristic — so the probability that all of them are composite is (1 - 1/log(NR^2/2))^N < (1 - 1/log(N))^N ≈ e^(-N/log N). Even with about N^2/2 chances for a counterexample, the expected number of counterexamples (union-bound) is only N^2e^(-N/log N), so for sufficiently large (even) N, the probability of the two drawings differing at any point should be vanishingly small. In fact, by this heuristic, we should expect only finitely many counterexamples, so quite likely the 10 above are the only ones.
- airesearcher 8y ago
  Here is animation by Ian Rust that shows how the pattern approaches GCD as the even values of n increase. https://streamable.com/l7r96 https://streamable.com/l7r96 Note that for odd values of n the pattern does not resemble GCD.

airesearcher 8y ago

Also there are versions in Perl and other languages in the Telegram group.

svat 8y ago

One correction (already accepted by your co-author @shaunxcode) is that even for even n, your triangle and the one formed by OEIS A054521 are not equivalent. Specifically, here are some values of N, and (row, column) coordinates where the gcd sequence and your sequence differ: Counterexample: N=14, (R,C) = (13, 3) Counterexample: N=20, (R,C) = (17, 8) Counterexample: N=20, (R,C) = (19, 1) Counterexample: N=30, (R,C) = (17, 7) Counterexample: N=30, (R,C) = (19, 1) Counterexample: N=38, (R,C) = (37, 8) Counterexample: N=44, (R,C) = (31, 2) Counterexample: N=44, (R,C) = (37, 2) Counterexample: N=50, (R,C) = (43, 13) Counterexample: N=74, (R,C) = (73, 43) (For n=74, look at the last shown row in the post right now, for N=73, where there's a “stray” red dot: this dot wouldn't be present in the computed-from-gcd sequence.) There are very few counter-examples though (larger ones seem hard to find); you can see some reasons in my long comment here: https://news.ycombinator.com/item?id=17106193 https://news.ycombinator.com/item?id=17106193 Here's a rough heuristic calculation for how many counterexamples we should expect. Let's say gcd(R,C)=1, so that there should be no “special reason” to expect everything in the set to be composite. Then, as the set contains N numbers each of size roughly (NR^2/2), each is prime with “probability” 1/log(NR^2/2) — this is the Cramer heuristic — so the probability that all of them are composite is (1 - 1/log(NR^2/2))^N < (1 - 1/log(N))^N ≈ e^(-N/log N). Even with about N^2/2 chances for a counterexample, the expected number of counterexamples (union-bound) is only N^2e^(-N/log N), so for sufficiently large (even) N, the probability of the two drawings differing at any point should be vanishingly small. In fact, by this heuristic, we should expect only finitely many counterexamples, so quite likely the 10 above are the only ones.

airesearcher 8y ago
Here is animation by Ian Rust that shows how the pattern approaches GCD as the even values of n increase. https://streamable.com/l7r96 https://streamable.com/l7r96 Note that for odd values of n the pattern does not resemble GCD.