$100,000 and 2^p -1

Post by Dan in NY
Posting
on Monday, May 15, 2006
Greetings,
I have a recreational, on-the-side puzzle suggested to me by a $100,000
"What is the smallest prime, p, such that 2^p -1 has ten million decimal
digits?" Please note that I am asking p to be prime but not 2^p -1. This
background information indicates my interest in the answer:-
The web site http://www.eff.org/awards/coop.php tells of prize money in
computing. Here are selected quotes from the site:- "50,000 to the first
individual or group who discovers a prime number with at least 1,000,000
decimal digits (awarded Apr. 6, 2000). $100,000 to the first individual or
group who discovers a prime number with at least 10,000,000 decimal digits."
See the site, http://www.mersenne.org/prime.htm for information about GIMPS,
the Great Internet Mercenne Prime Search. If you use GIMPS to find a
winning prime, you will share the prize.
As far as I know, the largest prime now published is 2^30,402,457 -1. It is
a Mersenne prime having 9,152,052 decimal digits; in binary, all its
30,402,457 bits are ones. The number 30,402,457 is itself a prime number.
It is possible -- I suppose it is very likely -- that the winning number for
this $100,000 prize will be a Mercenne prime. A Mercenne number is a
number, 2^p -1, where p is prime. If 2^p -1 is prime the number is a
Mercenne prime.
I would like to know the value of p for the "smallest" Mercenne number of at
least a million decimal digits, written as 2^p -1. I want to know a the
prime number, p, not any of the ten million digits of the Mersenne number.
AFAIK, only 43 Mersenne numbers are known to be prime. Please note that I
am asking a much simpler question than that of the prize; I am asking for a
Mercenne number, not a Mersenne prime.
I call this a puzzle because I have calculated an approximate answer to this
my number, p, is between 33,000,000 and 34,000,000. Also I want to learn of
the number and/or the method you use to find the answer to this puzzle.

What's wrong with just taking (log 2) of 10^10 000 000+1?

You might need an extended precision program is all.

Eg in Mathematica you type Log[2,10^10000000+1] and get
33219280.94887362347870319429489390175864831393024580 plus another 10 million or
so digits of precision if you want.

--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-***@egroups.com)

Dan in NY

2006-05-16 21:02:14 UTC

I think the OP wants to know the first prime which is greater
than 33,219,280, not just the first integer greater than it.
But if he can't even do that for himself, it seems unlikely that
he could have anything of much import to reveal afterwards.

33 219 281 is prime.
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere

&&&
Thanks for your replies, Patrick. You verified that my answer of 33,219,281
(as I write it in NY) is the answer to the puzzle. It is almost out of my
reach to determine whether numbers that large are prime.

I know that many things posted on Math usenet sites are requests to help
with tests and/or homework but I thought such protests from me would be
regarded with skepticism. In this case, I tried to turn a personal
curiosity of mine into a puzzle.

My desire to find this number is to be able to compare it to the next larger
prime announced and be able to tell whether it is large enough to have at
least 10,000,000 digits.

I have been following the new large primes being found using GIMPS related
to the $100,000 prize and part of my interest was to kindle interest in
anyone who reads the post and may be so inclined.

Before I posted the puzzle, I used a web site to find a list of primes
showing these four numbers as consecutive primes:-
33,219,253
33,219,281
33,219,283
33,219,313

I only found an approximate method for determining the number of digits for
2^p-1 using these primes. If Log[10,2^p] is rounded down to the nearest
integer does it give an exact answer?

You suggested that Log[2,10^10000000+1] be evaluated then gave its value
using Mathematica to evaluate it. Usually I use a spreadsheet, Quatro Pro,
to assist me but I have access to a computer that has Mathematica and (after
problems with a balky firewall) I was able to verify your answer to a few
digits beyond the decimal point. It seems as well to use Log[2,10^10000000]
(without +1) because it would take lots of precision to tell the difference.

Of course, as pointed out in the reply by bert, my puzzle asked for a prime
so it was sufficient to only include enough digits to be sure it wasn't
rounded up to reach 10,000,000 digits. Even though the puzzle asked for a
prime, an integer suffices to satisfy my curiosity. Rather by chance, the
smallest integer is prime, so if I had asked for the smallest such integer
exceeding a power of 2, the answer would be the same.

--
Dan in NY
(for email change t with g in
dKlinkenbert at hvc dot rr dot com)

Jens Kruse Andersen

2006-05-16 20:53:01 UTC

Post by Dan in NY
"What is the smallest prime, p, such that 2^p -1 has ten million decimal
digits?"
I would like to know the value of p for the "smallest" Mercenne number of
at least a million decimal digits, written as 2^p -1. I want to know a
the prime number, p, not any of the ten million digits of the Mersenne
number.

What's wrong with just taking (log 2) of 10^10 000 000+1?

It leads to a number with 10 000 001 digits.
(log 2) of 10^9 999 999 = 33219277.6269
The next prime is 33219281.
But 2^33219281 also has 10 000 001 digits.
So there is no answer to the first question which didn't say "at least".

The second question asks for at least a million digits.
(log 2) of 10^999 999 = 3321924.7730.
The next prime is 3321937.
So the answer is 2^3321937-1 which has 1 000 003 digits.
Good thing he didn't want "the ten million digits".
I would have been 8 999 997 short.

--
Jens Kruse Andersen

Dan in NY

2006-05-18 00:11:02 UTC

Post by Dan in NY
"What is the smallest prime, p, such that 2^p -1 has ten million decimal
digits?"
I would like to know the value of p for the "smallest" Mercenne number
of at least a million decimal digits, written as 2^p -1. I want to
know a the prime number, p, not any of the ten million digits of the
Mersenne number.

What's wrong with just taking (log 2) of 10^10 000 000+1?

It leads to a number with 10 000 001 digits.
(log 2) of 10^9 999 999 = 33219277.6269
The next prime is 33219281.
But 2^33219281 also has 10 000 001 digits.
So there is no answer to the first question which didn't say "at least".
The second question asks for at least a million digits.
(log 2) of 10^999 999 = 3321924.7730.
The next prime is 3321937.
So the answer is 2^3321937-1 which has 1 000 003 digits.
Good thing he didn't want "the ten million digits".
I would have been 8 999 997 short.
--
Jens Kruse Andersen

&&&

Greetings Jens,

Thank you for your reply. Because of it, I see an error in the my first
post of this thread, that I missed until now. I can't be sure, but you
probably figured that out. In the quote of my post above (from the
background information for the puzzle) where I said, "at least a million
decimal digits", I meant to write, "at least ten million decimal digits."

Also, you are correct that in my puzzle, I missed writing, "at least". I
didn't think it was an error because if a number has more than ten million
digits, it has ten million, but I should have been more clear. [That is, if
I have 15 eggs and I am asked whether I have a dozen eggs, I would likely
say, "Yes," even if the questioner didn't say, "at least."]

In your reply to Patrick's comment, "What's wrong with just taking (log 2)
of 10^10 000 000+1?", I was surprised at your reply, "It leads to a number
with 10 000 001 digits." It took me a few moments to realize what you
meant. "10^10 000 000+1" is a bit ambiguous but that hadn't occurred to me
when I read what Patrick wrote. I figured that the one really shouldn't be
added at all.

To clear up the ambiguity I am referring to, add parentheses after the "^".
But there are two ways to do this. Either "10^(10 000 000)+1 or "10^(10 000
000+1). If the "+1" is included inside as part of the exponent, I thought
it should have been added to make it "10^10 000 001" so I didn't consider
that idea. However, doing it that way does do what you said, it, "It leads
to a number with 10 000 001 digits."

I assumed I should put the "+1" after both parentheses. However, in doing
that, the "+1" becomes rather redundant because after taking Log 2, seeing
the difference between adding 1 or not adding it would require a lot more
precision than a few digits after the decimal point.

When you say, "But 2^33219281 also has 10 000 001 digits," I disagree with
you but I really do want to know whether you are correct. I think it has
exactly ten million digits and I could be wrong. In fact I posted my puzzle
partly in an attempt to verify that result of mine. Do you know of a
smaller integer (or prime) than 2^33219281 that has at least ten million
digits? I think the integer, 2^33219280, has 9 999 999 digits.

It is different to write this using a keyboard rather than a pencil and
paper; may lead to ambiguities. (With more complicated expressions that is
even more likely.) I should have stopped without keying in so many words
because the longer this is, the more likely I have made another mistake. If
anyone spots an error I would like to know but if we keep this going, I must
be careful because I might be beating it to death.

--
Dan in NY
(for email change t with g in
dKlinkenbert at hvc dot rr dot com)

Jens Kruse Andersen

2006-05-18 11:28:41 UTC

Post by Dan in NY
"What is the smallest prime, p, such that 2^p -1 has ten million decimal
digits?"
I would like to know the value of p for the "smallest" Mercenne number
of at least a million decimal digits, written as 2^p -1. I want to
know a the prime number, p, not any of the ten million digits of the
Mersenne number.

What's wrong with just taking (log 2) of 10^10 000 000+1?

It leads to a number with 10 000 001 digits.
(log 2) of 10^9 999 999 = 33219277.6269
The next prime is 33219281.
But 2^33219281 also has 10 000 001 digits.
So there is no answer to the first question which didn't say "at least".
The second question asks for at least a million digits.
(log 2) of 10^999 999 = 3321924.7730.
The next prime is 3321937.
So the answer is 2^3321937-1 which has 1 000 003 digits.
Good thing he didn't want "the ten million digits".
I would have been 8 999 997 short.

Thank you for your reply. Because of it, I see an error in the my first
post of this thread, that I missed until now. I can't be sure, but you
probably figured that out. In the quote of my post above (from the
background information for the puzzle) where I said, "at least a million
decimal digits", I meant to write, "at least ten million decimal digits."

Yes, I figured out what you meant. On Usenet, people may tease you by taking
badly formulated questions literally.

Post by Dan in NY
Also, you are correct that in my puzzle, I missed writing, "at least". I
didn't think it was an error because if a number has more than ten million
digits, it has ten million, but I should have been more clear. [That is, if
I have 15 eggs and I am asked whether I have a dozen eggs, I would likely
say, "Yes," even if the questioner didn't say, "at least."]

That's a non-mathematical context where the questioner probably just
wants to know whether you have enough eggs for something.
If you were asked "Do you have 9 fingers?", I'm guessing you would say
"No, 10" (assuming you actually do!).
Mathematics usually require precision to avoid such speculation.
Your question was: "What is the smallest prime, p, such that 2^p -1 has
ten million decimal digits?"
I think most mathematicians would interpret this as exactly ten million.

Post by Dan in NY
In your reply to Patrick's comment, "What's wrong with just taking (log 2)
of 10^10 000 000+1?", I was surprised at your reply, "It leads to a number
with 10 000 001 digits." It took me a few moments to realize what you
meant. "10^10 000 000+1" is a bit ambiguous but that hadn't occurred to me
when I read what Patrick wrote. I figured that the one really shouldn't be
added at all.
To clear up the ambiguity I am referring to, add parentheses after the "^".
But there are two ways to do this. Either "10^(10 000 000)+1 or "10^(10 000
000+1). If the "+1" is included inside as part of the exponent, I thought
it should have been added to make it "10^10 000 001" so I didn't consider
that idea. However, doing it that way does do what you said, it, "It leads
to a number with 10 000 001 digits."

No, it would give 10 000 002 digits.
How many digits in 10^2? In 10^3? See a pattern?

Post by Dan in NY
When you say, "But 2^33219281 also has 10 000 001 digits," I disagree with
you but I really do want to know whether you are correct. I think it has
exactly ten million digits and I could be wrong. In fact I posted my puzzle
partly in an attempt to verify that result of mine. Do you know of a
smaller integer (or prime) than 2^33219281 that has at least ten million
digits? I think the integer, 2^33219280, has 9 999 999 digits.

No, it has 10 000 000.
(log 10) (2^33219280) = 33219280*(log 10) 2 ~= 9 999 999.714
So 2^33219280 ~= 10^9 999 999.714
Remember the pattern?

--
Jens Kruse Andersen

Dan in NY

2006-05-19 06:32:20 UTC

Post by Dan in NY
"What is the smallest prime, p, such that 2^p -1 has ten million decimal
digits?"

-------------------------------------------------------------------------------
[I should have written the above question with "at least": "What is the
smallest
prime, p, such that 2^p -1 has at least ten million decimal digits?"]
-------------------------------------------------------------------------------
[text omited]

No, it has 10 000 000.
(log 10) (2^33219280) = 33219280*(log 10) 2 ~= 9 999 999.714
So 2^33219280 ~= 10^9 999 999.714
Remember the pattern?
--
Jens Kruse Andersen

&&&

Greetings Jen (and all who are still reading this thread),

Thank you again. Now we have a disagreement that I would like to pursue. I
might be about to learn that my pre-determined answer to this puzzle was
incorrect. Did I incorrectly pronounce someone the winner? Oh, well, I
said I posted it partly to verify my answer, so that is OK with me. However
it is after 2 AM. here and I realize I am not functioning well enough. I
need to think about this more after some sleep. If you are correct about
2^33219280 having ten million digits then I haven't yet seen the answer to
my puzzle.

If I don't see a smaller answer here, I may post this question in a new
thread.
What smallest possible value of an integer, n, so that 2^n has at least ten
million decimal digits?

--
Dan in NY
(for email change to with go in
dKlinkenbert at hvc dot rr dot com)

Dan in NY

2006-06-15 00:26:31 UTC

Post by Dan in NY
"What is the smallest prime, p, such that 2^p -1 has ten million decimal
digits?"
I would like to know the value of p for the "smallest" Mersenne
number
of at least a million decimal digits, written as 2^p -1. I want to
know a the prime number, p, not any of the ten million digits of the
Mersenne number.

What's wrong with just taking (log 2) of 10^10 000 000+1?

It leads to a number with 10 000 001 digits.
(log 2) of 10^9 999 999 = 33219277.6269
The next prime is 33219281.
But 2^33219281 also has 10 000 001 digits.
So there is no answer to the first question which didn't say "at least".
The second question asks for at least a million digits.
(log 2) of 10^999 999 = 3321924.7730.
The next prime is 3321937.
So the answer is 2^3321937-1 which has 1 000 003 digits.
Good thing he didn't want "the ten million digits".
I would have been 8 999 997 short.

Yes, I figured out what you meant. On Usenet, people may tease you by taking
badly formulated questions literally.

No, it would give 10 000 002 digits.
How many digits in 10^2? In 10^3? See a pattern?

No, it has 10 000 000.
(log 10) (2^33219280) = 33219280*(log 10) 2 ~= 9 999 999.714
So 2^33219280 ~= 10^9 999 999.714
Remember the pattern?
--
Jens Kruse Andersen

&&&
Greetings Jens and other readers,

Thank you Jens and others who read and considered my questions. (In the
following where I say 10^7 digits, I mean at least 10,000,000 decimal
digits.) I asked for the integer, m, in the smallest number of the form
2^m -1, having 10^7 digits. I also asked for the prime number, m, of the
form 2^m -1 having 10^7 digits.

It seems so simple, now. I see that 10^3 = 1,000 has three zeros but four
decimal digits. The pattern is that 10^n has n zeros but n +1 decimal digits
as indicated by Jens Kruse Andersen.

The smallest power of 2 having 4 decimal digits = 1 + Int(Log(base2, 10^3) =
10. 2^10 = 1024. The smallest power of 2 with d decimal digits = 1 + Int(Log
(base2, 10^(d-1)). The smallest power of 2 with 10^7 digits is 1 +Int(Log(
base2, 10^(9,999,999))). The smallest power of 2 with 10,000,001 decimal
digits is 1 +Int(Log( base2, 10^10,000,000)).

I have access to a computer with Mathematica. Using it, the smallest integer
with 10^7 digits is 10^(9,999,999) = 2^(33,219,277.63 ...). The smallest
integer with 10,000,001 decimal digits is 10^(10,000,000) = 2^(33,219,280.95
...).

These numbers are consecutive primes:
prime decimal digits
33,219,253 9,999,992
33,219,281 10,000,001
33,219,283 10,000,001
33,219,313 10,000,010

The smallest power of 2 with 10^7 digits = 33,219,278
The second power of 2 with 10^7 digits = 33,219,279
The third power of 2 with 10^7 digits = 33,219,280
The smallest power of 2 with 10^(10,000,001) decimal digits = 33,219,281

My conclusion from this is that the smallest number of the form 2^m -1
having 10^7 digits is 33,219,278 and the smallest number with m prime of the
form 2^m -1 having at least 10,000,000 digits has m = 33,219,281, having
10^7 +1 decimal digits. Thus I suppose that the prize winning first prime of
ten thousand or more digits - if it is a Mersenne prime - will have an
exponent larger than 33,219,281.

I apologize if I have mixed up the number and exponent or made some other
error. If you want more explanation, please ask me for it.

--
Dan in NY
(for email change t with g in
dKlinkenbert at hvc dot rr dot com)

Dan in NY

2006-06-17 22:55:04 UTC

"Dan in NY" <***@NY.net> wrote in message news:XO1kg.9491$***@news-wrt-01.rdc-nyc.rr.com...
[previous context snipped]

Post by Dan in NY
Greetings Jens and other readers,
Thank you Jens and others who read and considered my questions. (In the
following where I say 10^7 digits, I mean at least 10,000,000 decimal
digits.) I asked for the integer, m, in the smallest number of the form
2^m -1, having 10^7 digits. I also asked for the prime number, m, of the
form 2^m -1 having 10^7 digits.

[most of my post snipped]

Post by Dan in NY
My conclusion from this is that the smallest number of the form 2^m -1
having 10^7 digits is 33,219,278 and the smallest number with m prime of
the form 2^m -1 having at least 10,000,000 digits has m = 33,219,281,
having 10^7 +1 decimal digits. Thus I suppose that the prize winning first
prime of ten thousand or more digits - if it is a Mersenne prime - will
have an exponent larger than 33,219,281.
I apologize if I have mixed up the number and exponent or made some other
error. If you want more explanation, please ask me for it.
--
Dan in NY
(for email change t with g in
dKlinkenbert at hvc dot rr dot com)

&&&
Greetings to you,

I did mix up a number and its proper exponent. Above, in my conclusion, I
have spelled out an error. I wrote, "ten thounand or more digits" where I
meant, "ten million decimal digits." This was pointed out to me by private
email.

The late Senator Everett Dirkson once remarked, "A billion dollars here, a
billion dollars there, pretty soon, we're talking real money." For anyone
who would consider $50,000 to be real money, I could now write "a thousand
digits here and a thousand digits there and soon we're talking real money.

I had even named the file with my analysis of this method, "Ten thousand
digit prime," so I had actually made that mistake before I wrote the post.
Maybe I mixed-up the number of digits and the number of dollars in my head.

--
Dan in NY
(for email, exchange y with g in
dKlinkenbery at hvc dot rr dot com)

AGDer-2

2006-06-18 18:57:36 UTC

CONSTANTS OF DOUBLE DIGIT PRIME PROGRESSION

(P1, P2),(P3,P4)

|------|------|
| P1 | P2 |
|------|------|
| P3 | P4 |
|------|------|

(P1, P2)= Double DigitPrime Twins
(P3, P4)= Double DigitProgressive Prime Twins

(A,B/ C,D/ E,F)

A= (P3-P1)
B= (P4-P1)
C= (P3-P2)
D= (P4-P2)
E=A
F=D

B-C=4
A-C=2
B-D=2

{[(P3-P1) - (P3-P2)] + [(P4-P1) - (P4-P2)]}= [(P4-P1) - (P3-P2)]

What's wrong with just taking (log 2) of 10^10 000 000+1?

It leads to a number with 10 000 001 digits.
(log 2) of 10^9 999 999 = 33219277.6269
The next prime is 33219281.
But 2^33219281 also has 10 000 001 digits.
So there is no answer to the first question which didn't say "at least".
The second question asks for at least a million digits.
(log 2) of 10^999 999 = 3321924.7730.
The next prime is 3321937.
So the answer is 2^3321937-1 which has 1 000 003 digits.
Good thing he didn't want "the ten million digits".
I would have been 8 999 997 short.

Yes, I figured out what you meant. On Usenet, people may tease you by taking
badly formulated questions literally.

Post by Dan in NY
Also, you are correct that in my puzzle, I missed writing, "at least".

Post by Dan in NY
didn't think it was an error because if a number has more than ten million
digits, it has ten million, but I should have been more clear. [That

is,

Post by Dan in NY
if
I have 15 eggs and I am asked whether I have a dozen eggs, I would likely
say, "Yes," even if the questioner didn't say, "at least."]

Post by Dan in NY
me
when I read what Patrick wrote. I figured that the one really

shouldn't

Post by Dan in NY
be
added at all.
To clear up the ambiguity I am referring to, add parentheses after the "^".
But there are two ways to do this. Either "10^(10 000 000)+1 or

"10^(10

Post by Dan in NY
000
000+1). If the "+1" is included inside as part of the exponent, I thought
it should have been added to make it "10^10 000 001" so I didn't consider
that idea. However, doing it that way does do what you said, it, "It leads
to a number with 10 000 001 digits."

No, it would give 10 000 002 digits.
How many digits in 10^2? In 10^3? See a pattern?

No, it has 10 000 000.
(log 10) (2^33219280) = 33219280*(log 10) 2 ~= 9 999 999.714
So 2^33219280 ~= 10^9 999 999.714
Remember the pattern?
--
Jens Kruse Andersen

2^(33,219,280.95

Post by Dan in NY
...).
prime decimal digits
33,219,253 9,999,992
33,219,281 10,000,001
33,219,283 10,000,001
33,219,313 10,000,010
The smallest power of 2 with 10^7 digits = 33,219,278
The second power of 2 with 10^7 digits = 33,219,279
The third power of 2 with 10^7 digits = 33,219,280
The smallest power of 2 with 10^(10,000,001) decimal digits = 33,219,281
My conclusion from this is that the smallest number of the form 2^m -1
having 10^7 digits is 33,219,278 and the smallest number with m prime of the
form 2^m -1 having at least 10,000,000 digits has m = 33,219,281, having
10^7 +1 decimal digits. Thus I suppose that the prize winning first prime of
ten thousand or more digits - if it is a Mersenne prime - will have an
exponent larger than 33,219,281.
I apologize if I have mixed up the number and exponent or made some other
error. If you want more explanation, please ask me for it.
--
Dan in NY
(for email change t with g in
dKlinkenbert at hvc dot rr dot com)

Dan in NY

2006-05-16 21:36:17 UTC

"bert" <***@btinternet.com> wrote in message news:***@g10g2000cwb.googlegroups.com...
[omited]