mersenneforum.org 31 yr old N00b in Ohio
 Register FAQ Search Today's Posts Mark Forums Read

 2004-12-15, 16:34 #1 Unregistered   22×1,933 Posts 31 yr old N00b in Ohio Hello everyone. I am new to math period. I am trying to understand prime numbers and for the lack of high school education, I have decided to re-educate myself and go back to school. I have been getting pretty excited about math (but Im still learning fraction and stuff, dont laugh) , Now in class we are learning about prime numbers and Sieve of Eratosthenes. Her is my question, and what I am hoping for is if someone can explain in n00b terms what i am looking for and how to solve the equation. I simply just do not understand. Q: Find two prime numbers that, if multiplied, would generate a 400-digit number. A: WHAT????? thats like 1+399 zeros .... I really feel like a moron, but its extra credit and at my age I could use it. Now I am not asking for the answer, just help on how to get the answer or explanation. Thanks for any help. Kevin
 2004-12-15, 17:39 #2 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 23·17·79 Posts Well to start, when you multiply two numbers, the result has the number of digits that the two numbers have when added up (or one less). Examples: 2x2=4 (total digits are one less than the two numbers) 9x9=81 (same number of digits as the two numbers) 10x9=90 (one less) 10x10=100 (one less) 99x99=9801 (same) So based upon this you will need two numbers that total, at minimum, at least 400 digits. So, two 200 digit numbers may work or one that is 100 digits and the other is 300 digits, or a 1 digit number (like 7) and a 399 digit number. You could always go over the 400 digits. So you need some large prime numbers (or one real big one and a small one). Well, to check a 200 digit number with the Sieve is not practical (it would take a huge long time with a mess of computers working on it.) However, there are special ways of checking special numbers to see if they are prime (don't worry understanding how they work, I have taken math in college and don't understand them). So, you can stand on the shoulders of others and find two numbers that others know to be prime that are big enough. Many of these are often written in a short hand to make them easier to deal with. Mersenne numbers are one of those special types of numbers that are 'easy' to check. Mersenne numbers that are known to be prime have been found that are over a million digits long. So a finding a list of these may help out. Currently there are 41 Mersenne numbers that are known to be prime. Here is a list. (A quick simple way of explaining Mersenne type prime numbers. Start off with a number that you know to be prime (like 7). Multiply 2 by itself that number of times (2x2x2x2x2x2x2=128). Subtract 1 from that number (128-1=127). That number may be a prime. (In our case 127 is a prime). The 'shorter' way of writing this is 27 - 1 While this does not look short for 127, for bigger numbers it is much shorter. Sometimes you will see these numbers written as M(7) or M7 (my computer checked M17085791, not prime). Generally if you see a number below 45, like M41, they are refering to the 41st Mersenne known to be prime.) So on that list, if you find two numbers that are listed with more than 400 total digits in them, when multipled the result will be more than 400 digits. I hope that your teacher does not want you to do the actual multiplying of the numbers. So, if you find those numbers you could just write: "When you multiply 2xxx-1 and 2yyy-1 they will give a number about zzz digits long." (being sure to put the right numbers in for xxx, yyy and zzz) If you have any questions or don't understand something, ask us for more .
 2004-12-15, 17:44 #3 Xyzzy     Aug 2002 851410 Posts You can use python or bc (linux tools) to multiply large numbers like that... If you need exactly 400 digits it might be a bit harder, but getting more than 400 digits is easy... I'll post an example in a minute...
2004-12-15, 17:52   #4
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

23×17×79 Posts

Quote:
 Originally Posted by Xyzzy You can use python or bc (linux tools) to multiply large numbers like that...
Even if you only have an 8 digit calculator, there are ways to work on it in small bites. 'Way back in the day' (like 1860's) a mathematian would have given up their firstborn for an 8 digit that only did + - x and /

 2004-12-15, 17:53 #5 Xyzzy     Aug 2002 205028 Posts Code: mv@k8:~$echo '(2^1279-1)*(2^61-1)' | bc | tr -d '\\' | tr -d '\n' | wc -m 404 mv@k8:~$ echo '(2^1279-1)*(2^61-1)' | bc 23999057691437043876661270228354725329072966847810219092331342327863\ 04490674451611763672304468131546360233628463880709453092336859038755\ 75571657191828442384943773361315593251423587316189902226455640704252\ 27756119522520104180448640755347769295581004175496918933650381253972\ 54339236386504882329769383689499040679978710005625442316511236932615\ 4703884835496635679026863327960310554049193288289611721249652737 http://www.utm.edu/research/primes/m...dex.html#known
2004-12-15, 20:39   #6
amcfarlane

Nov 2004
UK

2·19 Posts

Quote:
 Originally Posted by Xyzzy [code]mv@k8:~$echo '(2^1279-1)*(2^61-1)' | bc | tr -d '\\' | tr -d '\n' | wc -m 404 mv@k8:~$ echo '(2^1279-1)*(2^61-1)' | bc [snip]...[/snip]
Don't you just love *nix command lines

2004-12-16, 23:20   #7
Unregistered

3×1,093 Posts

Quote:
 Originally Posted by Xyzzy [code]mv@k8:~$echo '(2^1279-1)*(2^61-1)' | bc | tr -d '\\' | tr -d '\n' | wc -m 404 mv@k8:~$ echo '(2^1279-1)*(2^61-1)' | bc http://www.utm.edu/research/primes/m...dex.html#known
This sounds interesting, but I guess I am just not understanding.

2^1279-1 = 1.0407932094664399081925240327364e+385

2^61-1 = 2305843009213693951

so in turn if I multiply them 2 nubers, it should give me a 400 digit number??

here is my problem...first, how does anyone get the first number (2^1279-1) <--- does this number get pulled out of a hat?? and then I also dont understand how would I swrite a 400 digit number..

GOSH... I feel so stupid in this area, but I badly want to understand.

any help is great and I do appreciate what everyone has said.

 2004-12-16, 23:37 #8 Unregistered   15AB16 Posts please forgive the questions, as I know that they may sound dumb but I am not as intelligent as some of you but I am trying hard. (2^1279-1) <-- on this particular number, is this a Mersenne prime? What makes it that? Is it because of the 2 that casifies it as such. Could a Mersenne number be a 7^1279-1 ?? I hope that my queston is understood. 31 yr old N00B in Ohio
 2004-12-16, 23:47 #9 Unregistered   2×32×241 Posts [QUOTE=Uncwilly] Sometimes you will see these numbers written as M(7) or M7 (my computer checked M17085791, not prime). Generally if you see a number below 45, like M41, they are refering to the 41st Mersenne known to be prime.) Okay here is another question. the paragraph above is saying that if I did a number like 2^127 -1 could also be written like M(127) ???
 2004-12-16, 23:58 #10 Unregistered   3×7×419 Posts okay another question. If 2^127 = 170141183460469231731687303715884105727 then why when calculated on my computer it omes up as 17014118346046923173168730371588e+38 alos, what is C4 as I have read that it equals 170141183460469231731687303715884105727 and C3 = 127 .... so could the a problem be written as follows ... 2C3=C4 ??? Maybe I have no grasp on this. But what does the "C" stand for and how do they work. C0 = 2 (prime) C1 = 3 (prime) C2 = 7 (prime) C3 = 127 (prime) C4 = 170141183460469231731687303715884105727 (prime) C5 > 1051217599719369681879879723386331576246 Meaning what or how is C0 equaling 2 .etc. Lots of questions today. LOL. Thanks for all of the help.
2004-12-17, 00:01   #11
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

1074410 Posts

Quote:
 Originally Posted by Unregistered 2^1279-1 = 1.0407932094664399081925240327364e+385 2^61-1 = 2305843009213693951 so in turn if I multiply them 2 nubers, it should give me a 400 digit number??
Yeah, 386 + 15 = 401 (and since the start of each number is low, 1 and 2, you will lose one digit, like I showed above).
Quote:
 Originally Posted by Unregistered here is my problem...first, how does anyone get the first number (2^1279-1) <--- does this number get pulled out of a hat??
Actually Xyzzy pulled that from the list that I pointed out, known Mersenne primes. As of today all numbers below 2^9,176,500 - 1 have been tested.
He just looked for two numbers that would make up a 400 digit number without being too big.
Quote:
 Originally Posted by Unregistered and then I also dont understand how would I write a 400 digit number.
You could copy the number that Xyzzy (Mike) posted above. Or you could write just the two numbers with an 'X' between, but use () around each number. It is valid to write large numbers in shorter forms like, 2 x 1012 instead of 2,000,000,000,000
Quote:
 Originally Posted by Unregistered GOSH... I feel so stupid in this area, but I badly want to understand. any help is great and I do appreciate what everyone has said.
First, asking for help shows that you are not stupid. You just don't know this stuff yet. This is the difference between ignorance and stupidity. Ignorance is the lack of knowledge and stupidity is being slow of mind.

The e+385 part of the number above is the same as writing 'x 10385'. It just tells how far to move the decimal. If the US nation debt is \$5,123,432,678,965 only the size and the first few numbers are important, so people say "5.1 trillion dollars". It is the same short hand idea. Seldom are anything more than the size and first 3 to 5 digits important for numbers.

Quote:
 Originally Posted by Unregistered Okay here is another question. the paragraph above is saying that if I did a number like 2^127 -1 could also be written like M(127) ???
Yes, it is one of those things that in math can be a little confusing. In English when you see the word 'read', you know how to say it 'reed' or 'red', based upon the context. In (higher) math same thing, there are things that need to be understood in context. (more in next post).

 Similar Threads Thread Thread Starter Forum Replies Last Post ThomRuley Msieve 1 2015-06-27 12:05 QuickCoder Hardware 15 2014-08-10 18:45 Andi47 Factoring 1 2007-03-22 20:58

All times are UTC. The time now is 18:20.

Mon Oct 3 18:20:54 UTC 2022 up 46 days, 15:49, 0 users, load averages: 1.40, 1.31, 1.26