mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2015-06-15, 22:52   #1
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

3,581 Posts
Default 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,...
only_human is offline   Reply With Quote
Old 2015-06-16, 10:31   #2
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

26E16 Posts
Default


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
File Type: pdf mersenneforum.pdf (125.8 KB, 90 views)
MattcAnderson is offline   Reply With Quote
Old 2015-06-16, 11:03   #3
axn
 
axn's Avatar
 
Jun 2003

17·281 Posts
Default

Yes. We can prove this using induction. Note that product(n=0,N-1, F(n)) = =M(2^n) = F(N)-2
axn is offline   Reply With Quote
Old 2015-06-16, 11:22   #4
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

3,581 Posts
Default

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/
only_human is offline   Reply With Quote
Old 2015-06-17, 17:49   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

419810 Posts
Default

IS THAT SO?
davar55 is offline   Reply With Quote
Old 2015-06-17, 17:54   #6
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

3,581 Posts
Default

Quote:
Originally Posted by davar55 View Post
IS THAT SO?
The question mark in the title is essential to presenting a puzzle. Or were you presenting a puzzle too?
only_human is offline   Reply With Quote
Old 2015-06-18, 17:55   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

Quote:
Originally Posted by only_human View Post
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
wblipp is offline   Reply With Quote
Old 2015-06-18, 18:12   #8
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

3,581 Posts
Default

Quote:
Originally Posted by wblipp View Post
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)
only_human is offline   Reply With Quote
Old 2015-06-26, 09:35   #9
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

3,581 Posts
Default

Quote:
Originally Posted by only_human View Post
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.
only_human is offline   Reply With Quote
Old 2015-06-26, 10:30   #10
davar55
 
davar55's Avatar
 
May 2004
New York City

10000011001102 Posts
Default

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
davar55 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Formubla-bla-bla to calculate the sum of two Prime numbers just by knowing the product Godzilla Miscellaneous Math 107 2016-12-06 17:48
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
Poulet numbers with 3 distinct prime factors flouran Math 10 2009-04-29 03:57
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25
Converting big numbers to and from binary and decimal 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.