Prime numbers

[septimus]

@Dr.Strangelove

I sorta reminded myself that I’d always been curious about a proof that triangular number probing (still quadratic, of course) hits every element in a 2^b size table.

I think I found an easy proof.

Given
0 <= a < a+c < 2^k
we want to show that the a’th and (a+c)'th triangular numbers are not congruent mod 2^k. Simpler is to multiply the triangular numbers by 2 (getting aa+a and aa+cc+2ac+a+c) and work with the difference. Thus we want to show that
c * (c + 2a + 1) is not a multiple of 2^(k+1)
But only one of the two factors is even and the larger factor (c + 2a + 1) is less than 2^(k+1) so can’t be a multiple thereof!

[Mijin]

@Thudlow_Boink

“Relevant” to what or to whom?

Prime numbers are the building blocks of all (whole) numbers, in somewhat the same way that the chemical elements are the building blocks of all chemical compounds.

Water is H[sub]2[/sub]O, and salt is NaCl.

10 is 2*5, and 24 is 2[sup]3[/sup]*3.

I am aware of this building block description (that all numbers can be formed as the product of primes).
But I still don’t see what’s so useful about that. Especially since, unlike chemical formulas, there are several alternative, valid descriptions e.g. we can arrive at all natural numbers using set theory.

[Dr.Strangelove]

@septimus

I think I found an easy proof.

Clever! I had to cheat and look at yours. I had been trying to look at binary patterns but only made minimal progress. The only interesting thing of note is that the two LSBs are the same as the standard Grey code. When you get to N=8, it’s almost a Gray code (just two indices swapped), and it diverges further from there but in an odd pattern.