mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2004-12-15, 16:34   #1
Unregistered
 

22×1,933 Posts
Default 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
  Reply With Quote
Old 2004-12-15, 17:39   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23·17·79 Posts
Default

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 .
Uncwilly is online now   Reply With Quote
Old 2004-12-15, 17:44   #3
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

851410 Posts
Default

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...
Xyzzy is offline   Reply With Quote
Old 2004-12-15, 17:52   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23×17×79 Posts
Default

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 /
Uncwilly is online now   Reply With Quote
Old 2004-12-15, 17:53   #5
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

205028 Posts
Default

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
Xyzzy is offline   Reply With Quote
Old 2004-12-15, 20:39   #6
amcfarlane
 
amcfarlane's Avatar
 
Nov 2004
UK

2·19 Posts
Default

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
amcfarlane is offline   Reply With Quote
Old 2004-12-16, 23:20   #7
Unregistered
 

3×1,093 Posts
Default

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.
  Reply With Quote
Old 2004-12-16, 23:37   #8
Unregistered
 

15AB16 Posts
Default

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
  Reply With Quote
Old 2004-12-16, 23:47   #9
Unregistered
 

2×32×241 Posts
Default

[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) ???
  Reply With Quote
Old 2004-12-16, 23:58   #10
Unregistered
 

3×7×419 Posts
Default

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.
  Reply With Quote
Old 2004-12-17, 00:01   #11
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

1074410 Posts
Default

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).
Uncwilly is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
N00b question ThomRuley Msieve 1 2015-06-27 12:05
N00B Question about system with multiple processors QuickCoder Hardware 15 2014-08-10 18:45
Unpacking and installing GGNFS? (error and n00b-questions) 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔