Is every product of distinct Fermat numbers symmetrical in binary?

[only_human]

Quote by David Richeson:
Here's what I learned today: Write out the mod-2 version of Pascal's triangle. That is, write out Pascal's triangle as usual and replace each even number with 0 and each odd number with 1. Then view each row as a binary number. This list of numbers is the full list of all products of distinct Fermat numbers. As we see in the figure the first several rows are 1, 3, 5, 15=3*5, 17, 51=3*17, 85=5*17, 255=3*5*17, 257,...

[MattcAnderson]

Every Fermat number is symmetric in Binary. F(n) = 2^(2^n)+1.
The first digit is a 1 then there are some zeros and finally another 1.
F(1) = 5 = 101 in base 2.
F(2) = 17 = 10001 in base 2.


Regards,
Matt

[axn]

Yes. We can prove this using induction. Note that product(n=0,N-1, F(n)) = =M(2^n) = F(N)-2

[only_human]

I know that every Fermat number is symetrical. What surprised me is that the product of multiple distinct Fermat numbers is also symetrical in binary.

Why did this surprise me? Because although only two bits are set in each Fermat number, when multiplying out a product of multiple distinct Fermat numbers, it seems that that there will be some carries to the left, but this result is still symetrical.

The statement that every possible product of distinct Fermat numbers is symetrical is implicit in the symmetry of Pascal's Table in my spoiler quoted section. Take a line of the table, perform a mod 2, on each entry, and the remaining even/odd bits of each entry grouped together as a binary string results is a symetrical binary number for that row and this number is also a product of distinct Fermat numbers.

I do admit that when something surprises me it usually means that I didn't understand it and that is why I immediately gave a quote that showed the implication that I titled the thread upon, so that even if I was off in the weeds somehow, I could intend to avert significant time expenditures but still present a puzzle. The thread title was intended to be an exception to Betteridge's law of headlines.

Betteridge's law of headlines is an adage that states: "Any headline that ends in a question mark can be answered by the word no." It is named after Ian Betteridge, a British technology journalist.

[davar55]

IS THAT SO?

[only_human]

Originally Posted by davar55

IS THAT SO?

The question mark in the title is essential to presenting a puzzle. Or were you presenting a puzzle too?

[wblipp]

Originally Posted by only_human

Why did this surprise me? Because although only two bits are set in each Fermat number, when multiplying out a product of multiple distinct Fermat numbers, it seems that that there will be some carries to the left,

Isn't this the faulty assumption? Multiplying them sequentially from smallest to largest, at each step the larger is so much larger that the two images of the smaller (using long hand "school" multiplication) never overlap, so there are never any carries.

[only_human]

Originally Posted by wblipp

Isn't this the faulty assumption? Multiplying them sequentially from smallest to largest, at each step the larger is so much larger that the two images of the smaller (using long hand "school" multiplication) never overlap, so there are never any carries.

Yes, you are exactly correct as fas as I understand things now and have answered the puzzle as I envisioned it being answered. It is a case where carries clearly don't at all occur when doing the multiplication in binary.

Perhaps it's not much of a puzzle but I think it is kind of pretty. The numbers remind of fractals or Gray Code tables in that the larger entries contain the earlier entries as substrings.

[only_human]

Originally Posted by only_human

Quote by David Richeson:
Here's what I learned today: Write out the mod-2 version of Pascal's triangle. That is, write out Pascal's triangle as usual and replace each even number with 0 and each odd number with 1. Then view each row as a binary number. This list of numbers is the full list of all products of distinct Fermat numbers. As we see in the figure the first several rows are 1, 3, 5, 15=3*5, 17, 51=3*17, 85=5*17, 255=3*5*17, 257,...

Afterward:
So how does one generate this list of all products of distinct Fermat Numbers?

Of all Gray Code tables, in my opinion, the most convenient Gray Code is based on
k = k XOR ( k >> 1 )
This keeps the most significant bit unchanged and the bit shifted off to the right that gets neglected during the calculation is unneeded for that result. But if you wanted an unchanged bit on both sides (and a wider result), it is easier to shift to the left like this:

k = k XOR ( k << 1 )

Why does this matter here? Because starting with k=1 and applying this line repeatedly generates the the exact values that are also generated from a Mod 2 operation on a normal Pascal's table:

in binary:

1
11
101
1111
10001
110011
1010101
...

This generates the numbers that I was looking at for this thread. As you can see, they are symmetrical and the above quoted reference has a link to a proof by induction that these numbers are a full list of products of distinct Fermat numbers:

In particular, the first 32 rows give all of the distinct products of Fermat primes. Thus they list the 31 known odd constructible polygons (obviously we skip the top row). [The 33rd row is Euler's composite Fermat number 4294967297.] Very cool!

Short proof by induction: http://oeis.org/wiki/Constructible_polygons

As an added bonus, the first 2^k rows of the mod-2 version of Pascal's triangle gives a nice approximation of the Sierpinski triangle.

[davar55]

If Fn = 2^2^n+1, then F0 = 2^2^0+1 = 3, F1 = 5, F2 = 17, F3 = 257, etc.

Then Fn = F0 * F1 * F2 * ... * Fn-1 + 2 for n >= 1.

So F0 * F1 * F2 * ... * Fn-1 is "all ones" in binary.

Since the "number of bits - 1" is 1, 2, 4, 8, 16, ... , 2^n for Fn,
their products of distinct Fn's never overlap in "bitspace."

There are no carries, so all such products remain symmetric.

After F4 = 65537, no higher Fn is known to be prime.
Their factors are not in general symmetric.

(I just noticed axn already said some of this. Hope the redundancy helps.)