mersenneforum.org Is every product of distinct Fermat numbers symmetrical in binary?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-06-15, 22:52 #1 only_human     "Gang aft agley" Sep 2002 3,581 Posts Is every product of distinct Fermat numbers symmetrical in binary? 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,...
2015-06-16, 10:31   #2
MattcAnderson

"Matthew Anderson"
Dec 2010
Oregon, USA

26E16 Posts

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
Attached Files
 mersenneforum.pdf (125.8 KB, 90 views)

 2015-06-16, 11:03 #3 axn     Jun 2003 17·281 Posts Yes. We can prove this using induction. Note that product(n=0,N-1, F(n)) = =M(2^n) = F(N)-2
2015-06-16, 11:22   #4
only_human

"Gang aft agley"
Sep 2002

3,581 Posts

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.
Quote:
 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.

Last fiddled with by only_human on 2015-06-16 at 12:15 Reason: s/advert/avert/ s/parity/even//odd/

 2015-06-17, 17:49 #5 davar55     May 2004 New York City 419810 Posts IS THAT SO?
2015-06-17, 17:54   #6
only_human

"Gang aft agley"
Sep 2002

3,581 Posts

Quote:
 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?

2015-06-18, 17:55   #7
wblipp

"William"
May 2003
New Haven

22·32·5·13 Posts

Quote:
 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.

Last fiddled with by wblipp on 2015-06-18 at 17:55

2015-06-18, 18:12   #8
only_human

"Gang aft agley"
Sep 2002

3,581 Posts

Quote:
 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.

Last fiddled with by only_human on 2015-06-18 at 18:32 Reason: forgot "not" "occur", deleted "all" as possibly ambiguous in "all the earlier", s/Grey/Gray/ (Frank Gray)

2015-06-26, 09:35   #9
only_human

"Gang aft agley"
Sep 2002

3,581 Posts

Quote:
 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:
Quote:
 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.

 2015-06-26, 10:30 #10 davar55     May 2004 New York City 10000011001102 Posts 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.) Last fiddled with by davar55 on 2015-06-26 at 10:32 Reason: credit axn

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 107 2016-12-06 17:48 ET_ Miscellaneous Math 40 2010-06-06 12:55 flouran Math 10 2009-04-29 03:57 T.Rex Math 4 2005-05-07 08:25 Quantum Skyline Math 5 2002-12-27 19:23

All times are UTC. The time now is 14:19.

Wed Nov 25 14:19:43 UTC 2020 up 76 days, 11:30, 3 users, load averages: 1.26, 1.33, 1.33