Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Fermat Divisor Search :
How is it possible to test divisibility on such huge numbers?
Author 
Message 

If I understand correctly, F5523858, the number we found a divisor for a while ago, has something in the ballpark of 10^1660000 digits. That's more digits than there are atoms in the universe  by a LOT. How are we able to determine that the prime we found divides this number if we can't even come close to representing the number in full?
Sorry if this is a silly question, I'm just a bit curious as to how it's possible.
____________
1 PPSE (+2 DC) & 5 SGS primes  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 672 ID: 164101 Credit: 305,042,960 RAC: 0

The answer is Modular exponentiation  


The answer is Modular exponentiation
Could you please specify a link that's not blocked in China?
____________
SHSIDElectronicsGroup@outlook.com
waiting for a TdP prime...
Proth "SoB": 44243*2^440969+1
 


The answer is Modular exponentiation
Awesome, thank you for linking that video! That explained the process very clearly.
Could you please specify a link that's not blocked in China?
Well, it's a YouTube video, so you might not have much luck with finding one. You might be able to search online for "YouTube unblock" or mirror services that aren't blocked in China, but I don't know how successful that will be.
It appears there's a Wikipedia article on the same topic  I've got no idea whether Wikipedia is blocked for you or not. There's also a Chinese Wikipedia version of that article.
____________
1 PPSE (+2 DC) & 5 SGS primes  

KEPSend message
Joined: 10 Aug 05 Posts: 293 ID: 110 Credit: 9,443,250 RAC: 2,891

If I understand correctly, F5523858, the number we found a divisor for a while ago, has something in the ballpark of 10^1660000 digits. That's more digits than there are atoms in the universe  by a LOT. How are we able to determine that the prime we found divides this number if we can't even come close to representing the number in full?
Sorry if this is a silly question, I'm just a bit curious as to how it's possible.
There may be a language barrier, but do you really mean that there is less than 16,600,000 atoms in the universe?
You can always represent a 16,600,000 digit number in full, unless you refer to something other than decimal exspansion  is that the case?
I did some googling and unfortunantly I couldn't find a count of the amount of atoms per single human... however I did find a count for a Liter of water and that is: 1.0038*10^26, wich is way more than 16,600,000 atoms. I'm asking you, because there may be something I miss and you are not the first one on this forum claiming that a number with relatively few digits cannot be represented in full, due to requiring more atoms than excists in the universe. So please elaborate and see if I can in fact learn something :)
Ps. It appears that all the water on Earth contains around: 1.40532e+47 atoms. (There appears to be about 1.4 billion cubic kilometers of water on Earth)
Pps. The sun contains 10^57 atoms and the visible stars in the univers apparently contains, 10^78 to 10^82 atoms :) ... in addition to that we have to add all that we cannot see, black holes, asteroids, exoplanets, comets etc.
A little fun for a rainy day: https://www.nasa.gov/sites/default/files/atoms/files/black_hole_math.pdf  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 176 ID: 1108183 Credit: 10,207,198 RAC: 5,098

If I understand correctly, F5523858, the number we found a divisor for a while ago, has something in the ballpark of 10^1660000 digits. That's more digits than there are atoms in the universe  by a LOT. How are we able to determine that the prime we found divides this number if we can't even come close to representing the number in full?
Sorry if this is a silly question, I'm just a bit curious as to how it's possible.
There may be a language barrier, but do you really mean that there is less than 16,600,000 atoms in the universe?
Not 1660000 digits. 10^1660000 digits. That is much, much larger than 10^80.
But Yves is of course correct: modular exponentiation allows us to study a 10^1660000digit number while only needing to store some roughly 1660000digit numbers in our computer's memory.  


A. The number of atoms in the universe is a number with 80 digits.
B. The small factor of F(5523858) we found is 13*2^5523860 + 1. The small factor has 1662849 digits. So the small factor is incomprehensibly larger than the number of atoms in the universe (80 digits).
C. The number F(5523858) which the small factor divides, is:
F(5523858) = 2^(2^5523858) + 1
The problem here is, I cannot write how many digits F(5523858) has. If I were to do that, I would need to type in here 1662847 keypresses, making my post more than 1.6 megabytes long (in ASCII). If I resort to socalled scientific notation, the number of digits in F(5523858) is about 2.6816*10^1662846.
/JeppeSN  


A. The number of atoms in the universe is a number with 80 digits.
B. The small factor of F(5523858) we found is 13*2^5523860 + 1. The small factor has 1662849 digits. So the small factor is incomprehensibly larger than the number of atoms in the universe (80 digits).
C. The number F(5523858) which the small factor divides, is:
F(5523858) = 2^(2^5523858) + 1
The problem here is, I cannot write how many digits F(5523858) has. If I were to do that, I would need to type in here 1662847 keypresses, making my post more than 1.6 megabytes long (in ASCII). If I resort to socalled scientific notation, the number of digits in F(5523858) is about 2.6816*10^1662846.
/JeppeSN
For a real brain bender: there isn't enough space in the universe to represent the short form notation of any description of Graham's Number; not even an approximation of the number of digits.
And yet, there are still larger numbers of mathematical significance that make it quite infinitesimal by comparison.
____________
Eating more cheese on Thursdays.  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 462 ID: 1241833 Credit: 280,036,000 RAC: 537,656

A. The number of atoms in the universe is a number with 80 digits. This nicely shows how the human mind (at least my mind) struggles with exponentials. I recently read the human body has 10^24 atoms, so my first thought was, the universe cannot be just 10^80!
But of course that's true. Our planet earth contains 10^50 atoms, our galaxy 10^65 atoms and the whole universe 10^80 atoms.
So each human has a 24 digit number of atoms and the whole galaxy 65 digits number of atoms. Sounds weird to me. :)
It also makes you appreciate how much larger a Proth prime with n = 1000000 is than one with n = 900000 even though they seem roughly the same size if you tend to think in number of digits. But these few digits really pack a punch.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,800,000  


So each human has a 24 digit number of atoms and the whole galaxy 65 digits number of atoms. Sounds weird to me. :)
One needs to get used to this stuff. 65 minus 24 is 41. So you are saying a galaxy is the same as 100000000000000000000000000000000000000000 humans (trying to type fortyone zeros here). Galaxies are not so small. /JeppeSN
 

KEPSend message
Joined: 10 Aug 05 Posts: 293 ID: 110 Credit: 9,443,250 RAC: 2,891

If I understand correctly, F5523858, the number we found a divisor for a while ago, has something in the ballpark of 10^1660000 digits. That's more digits than there are atoms in the universe  by a LOT. How are we able to determine that the prime we found divides this number if we can't even come close to representing the number in full?
Sorry if this is a silly question, I'm just a bit curious as to how it's possible.
There may be a language barrier, but do you really mean that there is less than 16,600,000 atoms in the universe?
Not 1660000 digits. 10^1660000 digits. That is much, much larger than 10^80.
But Yves is of course correct: modular exponentiation allows us to study a 10^1660000digit number while only needing to store some roughly 1660000digit numbers in our computer's memory.
Yes, 10^1660000 = 1,660,001 digits. So we are back to the question, why state that representing the number in full takes up more digits than there is atoms in the universe? We only need 1,660,001 bytes or 13,280,008 bits to represent the number in full. I'm asking, because I'm feeling a growing anoyance about the statement that numbers can not be represented in full due to taking up much more digits than can be represented by atoms in the universe, if 1 atom was representing 1 digit. So again, if anything, what am I missing?  

Nick Send message
Joined: 11 Jul 11 Posts: 1007 ID: 105020 Credit: 2,738,348,680 RAC: 9,116,839

Yes, 10^1660000 = 1,660,001 digits.
It is 1 with 1,660,000 zeroes after it. It is a representation of the quantity. Each 1 of those 1660000 digits means a multiplying of 10 if you were to write X 10^1660000 times.
A million is 10^6
If I wanted to write X a million times that would take a while.
And if I did that 10 times I would be at 10^7
Edit: My brain has melted.  


If I understand correctly, F5523858, the number we found a divisor for a while ago, has something in the ballpark of 10^1660000 digits. That's more digits than there are atoms in the universe  by a LOT. How are we able to determine that the prime we found divides this number if we can't even come close to representing the number in full?
Sorry if this is a silly question, I'm just a bit curious as to how it's possible.
There may be a language barrier, but do you really mean that there is less than 16,600,000 atoms in the universe?
Not 1660000 digits. 10^1660000 digits. That is much, much larger than 10^80.
But Yves is of course correct: modular exponentiation allows us to study a 10^1660000digit number while only needing to store some roughly 1660000digit numbers in our computer's memory.
Yes, 10^1660000 = 1,660,001 digits. So we are back to the question, why state that representing the number in full takes up more digits than there is atoms in the universe? We only need 1,660,001 bytes or 13,280,008 bits to represent the number in full. I'm asking, because I'm feeling a growing anoyance about the statement that numbers can not be represented in full due to taking up much more digits than can be represented by atoms in the universe, if 1 atom was representing 1 digit. So again, if anything, what am I missing?
The number isn't a paltry 1660001 digits, it's 10^1660000 digits. A megaprime is 10^6 digits. For scale, a number with 10^185 digits is enough to fill the universe. This one is 10^1659815 times longer.
____________
Eating more cheese on Thursdays.  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 176 ID: 1108183 Credit: 10,207,198 RAC: 5,098

The number of atoms in the universe is approximately 100000000000000000000000000000000000000000000000000000000000000000000000000000000. That's a pretty big number. In my browser, it's big enough to take up most of one line.
The Fermat divisor we discovered, 13*2^5523860+1, has 1662849 digits. Not too big. There is plenty of space in the universe to store that many digits. In fact you can see all 1662849 digits here.
The Fermat number it divides, F5523858, is a different story. If you go back to the link above and scroll all the way through, that is a rough estimate of how many digits F5523858 has. To repeat: that monstrosity that you just spent 20 seconds scrolling through is approximately the number of digits in F5523858. It is far greater than 100000000000000000000000000000000000000000000000000000000000000000000000000000000, or any other conceivable measure of the size of the universe.  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 462 ID: 1241833 Credit: 280,036,000 RAC: 537,656

One needs to get used to this stuff. 65 minus 24 is 41. So you are saying a galaxy is the same as 100000000000000000000000000000000000000000 humans (trying to type fortyone zeros here). Galaxies are not so small. /JeppeSN Apparently they are. Or rather, 10^41 is an incredible large amoint of humans.
But I'm beginnign to mistrust the numbers. So: a human contains 62 at% H, 12 at% C and 24 at% O. So we can calculate an average atomic weight of 0.62 * 1 + 0.12 * 12 + 0.24 * 16 = 5.9. Let's say 6 g/mol.
So a 60 kg human contains 10000 mol atoms which is 1E4 * 6E23 = 6E27. Even more than I previously quoted.
So the whole universe weighs as much as 100000000000000000000000000000000000000000000000000000 humans. Unless your 10^80 was wrong in the first place. ;)
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,800,000  

Nick Send message
Joined: 11 Jul 11 Posts: 1007 ID: 105020 Credit: 2,738,348,680 RAC: 9,116,839

Time to take this to the absurdist level.
I am worried about what the universe would be like if it was actually made of humans?
There would be no walking to the toilet in the middle of the night while in a state of nature. The walls would complain "Get some clothes on!"
No more sleeping in because the bed would be having an argument with itself.
Taking a favourite snack out of the fridge would get derision.
I am glad the universe hasn't taken the choice to arrange it's atoms in entirely human forms.
I think most people can understand numbers up until the size gets too big to comprehend in terms of things they know day to day. For me, I think much beyond 10^12 isn't easy to place. $10^12 is approx monetary size of the largest companies, or medium size economies. 10^12 calories is approx size of a recent explosion.
I 'know' that a mol is 6.02 x 10^23 particles, but I think I don't properly comprehend that number.  

Post to thread
Message boards :
Fermat Divisor Search :
How is it possible to test divisibility on such huge numbers? 