Hacker News new | past | comments | ask | show | jobs | submit login

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

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.



Here is animation by Ian Rust that shows how the pattern approaches GCD as the even values of n increase.

https://streamable.com/l7r96

Note that for odd values of n the pattern does not resemble GCD.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: