81–90 of 195 posts
It wasn't exactly clear to me when I read the article, so here's my explanation: - take a line of integers, color them black if prime, red otherwise - hexagonally arrange them in a spiral (similar to Ulam's spiral) - cut the hexagon into six equilateral triangles - overlap the triangles (rotate where necessary) - if any pixels are black, color the whole thing black, if none are black, color it red - interesting patte…
Earlier quoted context omitted.
But that does produce a picture identical to theirs. Because they are using 75 numbers per square, they do end up hitting at least one prime in each box with (n,k)=1 for the first 75 rows. This pattern won't continue much longer, which is why they've conveniently stopped the picture at that point.
The claim is that using N numbers per square will result in the pattern holding for N rows, for arbitrarily large N.
n = 14: fails on row 13, col 3
n = 20: fails on row 17, col 8
n = 30: fails on row 17, col 7
n = 38: fails on row 37, col 8
n = 44: fails on row 31, col 2
n = 50: fails on row 43, col 13
…
This just shows the reduced residues mod n. There are n squares in the nth row from the top. Color the kth square of the nth row black if gcd(k,n)=1, color it red otherwise.
Earlier quoted context omitted.
But that does produce a picture identical to theirs. Because they are using 75 numbers per square, they do end up hitting at least one prime in each box with (n,k)=1 for the first 75 rows. This pattern won't continue much longer, which is why they've conveniently stopped the picture at that point.
Can you explain how that picture would be produced with 75 numbers per square? The generalization that seems obvious to me already fails in both cells of row 2, because 75 is odd: row 1, col 1: [1, 2, 3, …, 75], has primes row 2, col 1: [76, 78, 80, …, 224], no primes row 2, col 2: [77, 79, 81, …, 225], has primes
Earlier quoted context omitted.
Can you explain how that picture would be produced with 75 numbers per square? The generalization that seems obvious to me already fails in both cells of row 2, because 75 is odd: row 1, col 1: [1, 2, 3, …, 75], has primes row 2, col 1: [76, 78, 80, …, 224], no primes row 2, col 2: [77, 79, 81, …, 225], has primes
You are completely right; their pattern holds iff (I believe, not proven!) the number they take 75 for is even . If you take any even number of rows (== amount of numbers per cell, in their construction), say 6, or 74, or 76, the pattern works.
> on January 18, 2018, I found a numerical sequence that generated the exact same pattern as Shaun’s pattern Does this mean that we have a sort of bloom filter-esque test for primality? (ie, it will give you a guaranteed no in O(1) but you'll have to crunch numbers to get the yes?) If so, are there implications for things that want to know "is it prime?" quickly? Crpytography comes to mind, for instance...
>Does this mean that we have a sort of bloom filter-esque test for primality? This catches most non-primes ;) bool maybe_prime(x) { return x % 2 && x % 3 && x % 5 && x % 7; }
Earlier quoted context omitted.
You are completely right; their pattern holds iff (I believe, not proven!) the number they take 75 for is even . If you take any even number of rows (== amount of numbers per cell, in their construction), say 6, or 74, or 76, the pattern works.
No, it still fails for even n; see my other comment: https://news.ycombinator.com/item?id=17104624
Then their claim that this pattern holds isn't even true; as pointed out elsewhere, and is obvious when you write out the sequence items explicitly in terms of their coordinates, any gcd!=1 cell will be red. But a gcd=1 cell need not be black, for many n.
My take, but correct me if I'm wrong. Take the relation to the GCD triangle http://oeis.org/A054521 At GCD(n,k)!=1 all numbers are divisible by GCD(n,k) therefore contains no prime At GCD(n,k)==1 we have https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith... - so those series contain infinitely many primes - and seems like they actually contain at least one prime in all the pixels of the first N rows (but th…
So their picture is nice, and the gcd!=1 cells are all red, but the gcd=1 cells need not be black. For odd N this fails loads of times (always?), and for even N you quickly find failing cells when you start looking for it (see linked comment).
Earlier quoted context omitted.
The claim is that using N numbers per square will result in the pattern holding for N rows, for arbitrarily large N.
Even if I’m misunderstanding how this is supposed to work for odd n, this claim fails for plenty of even n. n = 14: fails on row 13, col 3 n = 20: fails on row 17, col 8 n = 30: fails on row 17, col 7 n = 38: fails on row 37, col 8 n = 44: fails on row 31, col 2 n = 50: fails on row 43, col 13 …