challenge



#31

OK, here is the challenge. 1741^9 is equal to the sum of 9 consecutive prime numbers. What are they?

Without using a computer or CAS calculator, please.


#32

Youch they are big.

    1741^9 = 146,956,547,386,947,872,723,891,185,261

So the numbers will be around:

    16,328,505,265,216,430,302,654,576,140


There must be a short cut...


- Pauli


#33

I'm hoping someone can dazzle us.


#34

I've got them but I resorted to Wolfram Alpha's first prime larger than joy. Interestingly, it doesn't understand first prime smaller than.

Now to figure out how on a calculator...

- Pauli

#35

Quote:
Youch they are big.

    1741^9 = 146,956,547,386,947,872,723,891,185,261

So the numbers will be around:

    16,328,505,265,216,430,302,654,576,140

There must be a short cut...

- Pauli


Not quite; this assumes that the primes are approximately the same order of magnitude and evenly distributed. The nth prime is approximately n*log(n).


#36

Actually they are around that number, the primes are consecutive which means they must lie around about the target number over nine.


- Pauli


#37

Not to give too much away. But 5 are below and 4 above.


#38

ok, let N = 1741^9. mod(N, 9) = 1, so write N = 9k + 1 with k = floor(N/9). and k is paul's number earlier. k is not prime.

now make a table P-k, where P prime greater than k and smaller than k, say 7 each way. i get:

P-k, P > k
151, 191, 193, 229, 343, 349, 391
P-k, P < k
-17, -49, -131, -253, -313

need to find a combination of the above that sum to 1, so that sum (P-k_i) = 9k + 1.

a quick scan shows first 4 of from the first list and first 5 of the second list do this. ie 151+191+193+229-17-49-131-313-253 = 1

so the desired numbers are k with each of these added.

16328505265216430302654576291
16328505265216430302654576331
16328505265216430302654576333
16328505265216430302654576369
then
16328505265216430302654576123
16328505265216430302654576091
16328505265216430302654576009
16328505265216430302654575887
16328505265216430302654575827

it was a bit lucky that the ones immediately up and down were the answers.

Edited: 16 Apr 2010, 9:25 a.m.


#39

Now that the answer is exposed here is my WolframAlpha input:

Sum[NextPrime[1741^9/9,i],{i,1,4}]+Sum[NextPrime[1741^9/9,i],{i,-5,-1}]

#40

presumably, there's no way to perform the search for the actual values in the summation. if they weren't so lucky to be centred around the mean, it would have been much harder to find them.

Although i used my calculator to perform the prime tests, i wonder if there's a short cut. for example, we have to find primes (1741^9)/9 + a, for relatively small `a'. it seems that all composite such numbers for small a have small divisors (note 1741 is prime). is this significant?


#41

Quote:
Although i used my calculator to perform the prime tests

Which one, a 50g?

Don stated the challenge so as to not use a CAS calculator. This would require writing some 30-digit math routines and programing a probabilistic primality test routine using them. That is, unless there's some really clever short cut.

-Katie


#42

Displaying long numbers is one of Hugh's specialities. He has several bits of software that do that, e.g. Scicalc, Exact and Reckon. Reckon on the fx-9860G/Gii (listed as non-CAS) displays the full 30 digits (Reckon on my 9860GII was the first thing I reached for when I read the challenge). It also has a factoring function and a prime number checking function, that can take these many digit numbers as arguments.


#43

I used my own of course :-)

I'm using Reckon on the 9860g. I haven't developed a CAS for it yet (although i do have some work in this direction). However, it does support big ints and has some factoring code.

you are correct, that the "prime" test method uses a probabilistic algorithm. to reject composites i use a strong pseudoprime test up to the Riemann limit = min(floor(2ln(n)^2), n-1) or 50 trials whichever is the smallest. 50 is an arbitrary number for confidence. hand waving theory says this gets 2^-50:1 of being wrong. i'd like to do more trials, but calculators are slow.

however, you can just punt the number to the "fac" method, which attempts factorisation (it's also short to type than "prime"). the fac method uses a series of approaches including prime testing.
firstly, "fac" attempts trial division. for this i use my "division without division" method to find any factors up to 2^20. here's an article on this method i wrote a while back

http://www.voidware.com/hpcc/smallfactor.pdf. Actually this approach is suitable for factoring any number up to 12 digits in length in under 10 seconds, but not for larger numbers.

if the above fails to find a factor, the strong pseudo prime test is applied, either up to the Riemann limit or 50. if it thinks the number is prime, then the process stops. most often the method finds a "witness" for a composite, in which case prime testing quits and we move on.

if we get past the trial division and prime test, then we have a composite with a factor > 2^20. now we're in trouble! my old code used to use a bunch of methods including pollard rho, Fermat and shanks' square free method. since then ive implemented Lenstra's elliptic curve method (ECM) and, without a doubt, this method dominates all others. the other attempts are no longer attempted and "fac" moves right away to the ECM.

the ECM is the third best known factoring method. unfortunately the other two, the quadratic sieve, and (general) number field sieve cannot be implemented on calculators because they require a large amount of memory. the ECM requires hardly any and is a very beautiful method which has running time proportional to the smallest factor - a highly desirable property!

the theory and efficient implementation are covered in Crandall & Pomerance, "prime numbers", chapter 7, 2nd edition. the authors develop a number of important optimisations to the method. i have followed these in my implementation but i have not gone as far as the Montgomery arithmetic (it's totally weird!)

if you want to try this out,

checkout http://www.voidware.com/reckon/ for the casio

or for the PC exe get,
http://www.voidware.com/reckon/reckon.exe

try these

a=1741^9-1
a=a/9+151
prime(a)
or fac(a)

also try,
a=2^73-1
a=a/439
fac(a)

or even
fac(2^103-1)


Bart, thanks for the comments. FTI, i just uploaded a new reckon casio binary 1.15 no actual change except that i just noticed it was suddently taking a _lot_ longer to factor numbers. turned out it was the escape key test i put in recently (you can press "EXIT" whilst factoring to abort). this _really_ slowed it down, so i moved this test out of an inner loop and its fine now.


#44

Hugh,

I just downloaded your new code, very nice and fast!

But I tired:

x=9999999967^2
fac(x)

and while prime(x) returned 0, fac(x) returned 99999999340000001089. I was expecting 9999999967. Is that wrong?

-Katie


#45

Hi Katie,

You're not wrong. looks like it failed to factor this one. the number returned was the original number. However, i wondered why it failed on this, because this value is within its range. turns out that Lenstra's ECM doesnt work for exact powers! That will teach me to read the small print :-)

so, i've added an extra test for the number being p^n. For example i tried x=1048583^3. This didn't factor before either (v1.15), but now it does.

I've uploaded v1.16 with these fixes both for the casio and reckon.exe (same links as before).

thanks - another bug squashed!


#46

What a speedy bug fix!

Funny thing is, the 50G (ver 2.09) has a similar bug, I think. The 'factors' function thinks 9999999967^2 is prime and it takes its time to reach this conclusion.

I found a CAS for the ipod touch that's got most of the functionality of the CAS in the 50G and is really fast, PocketCAS pro ($5), it gets this problem right! Wolfram Alpha is now cheap, but you need to have wifi access for that.

-Katie


#47

Thanks for that bug, it's interesting that ISITPRIME says 0. and
PREVPRIME and NEXTPRIME give numbers 2 below and 24 above the
number in question. After the 35s bug exposition and continued finding of new bugs, it's fun to poke at the "revered" 50g. :-)

#48

Thanks Hugh. You have much fascinating material here, it will take some time to review it all, but I'm going to work on it.

Don

#49

Hugh, I just downloaded your latest Reckon to my slim. Great product! How did you find the primes > 1741^9/9? When I do this I get this:

x=1741^9/9
1632.....140+1/9 response
np(x)
1632.....140+1/9 same response??
I expected 1632....576291

#50

it wont touch the number if its not an integer.

try,

1741^9-1
ans/9

then

np(ans)

keep doing this for a list of the primes, then repeat with pp(n) for the previous primes.


#51

Thanks, Hugh, I'll try that.

Don

#52

Quote:
presumably, there's no way to perform the search for the actual values in the summation. if they weren't so lucky to be centred around the mean, it would have been much harder to find them.

They must lie around 1741^9/9. Nine numbers less than 1741^9/9 cannot sum to 1741^9. Likewise for over.

This leaves the either possibilities of 8 below & 1 over through to 1 below and 8 over. I.e. 16 primes in total. Moreover, the search can be trimmed once you start finding primes and discover they are near to 1741^9/9 both above and below.

- Pauli

#53

Quote:
Without using a computer or CAS calculator, please.

OK.

1741^9 is about 1.4696E29 on my HP28S.
The nine consecutive primes numbers are around 1.6329E28.

I win the cahllenge ?


That's all the 12 digits precision of my advance scientifc calculator (not a CAS computer !) can tell to me.

OK. No I am not the winner !

Knowing that my HP28S needs nearly 21 min to test primality of 9999999967, I expected about 7 days to test a prim number around 1.6329E28. So seeking for these nine consecutive prim numbers will be about 3 months !

OK.

What's the trick to solve this challenge on any classic HP in a week-end ?


#54

Quote:
What's the trick to solve this challenge on any classic HP in a week-end ?

I don't know if it actually can be solved on a non-CAS calculator, but I know there is a lot of brain power among people who participate in this forum, so I'm hoping some genius among us will hit upon a way of approaching this particular problem that nobody has thought of before. Hey, if the NSpire CAS or the 50g can test primality for a big number in a few seconds then, theoretically, why can't the 30b? Maybe (probably) it will take re-purposing it, or the 12c for that matter. But can it be done? If it can, and somebody figures out how to do it, I think that will be noteworthy.

Hugh, didn't you repurpose the Casio 9860 to do some factoring with large integers? Can it do this problem?

As they said in "A Beautiful Mind," who among you will be the next Einstein?


#55

Hi Don,

yes, i did repurpose the casio and that's the machine i used to help me solve this problem. actually i had to manually search the neighbourhood for primes using the prime test.

Absolutely, the 30b could solve this problem with some repurposing. it's actually faster than the casio. a while back i tried to implement a couple of factoring programs on the hp30b in the user mode programming language. however, the problem is that, working with 12 digits you can only perform arithmetic on a 6 figure integer before it overflows the mantissa and you get the wrong answer. this is fine for trial division because you know there's a factor in 6 figures or it must be prime. However, i tried getting pollard rho working, but this requires arithmetic mod N and then you get overflow.

in the end i did write a home-brew multiprecison workaround, but it wasn't really going to solve the show. we just have to persuade HP to put some factoring code in the roms :-)

or implement our own (scientific) calculator on the hp30b - which im thinking of doing for fun :-)

#56

The ALG48.LIB is about 50K. I'm afraid it won't fit into your HP-28s. However you need only a small set of functions out of it. So it might be possible to make them fit.

I doubt that a probabilistic primality test (e.g. Miller-Rabin) will take 21 minutes for 9999999967 even on a 28s.

Cheers

Thomas

#57

Here's a program for an HP-48gx with the ALG-library installed:

\<< \-> n
\<< n 9 ADIV @ a good starting point
{ }
1 9
START @ build a list of nine consecutive primes
SWAP PRIM+
DUP ROT
+
NEXT
SWAP DROP
DO @ try previous prime
DUP TAIL
SWAP DUP
SIZE GET PRIM-
+ DUP
\<< AADD \>> STREAM
UNTIL
n SWAP / B\->R
END
REVLIST
1 \<< Z<->S \>>
DOLIST
\>>
\>>

Enter #1741d 9 APOW and run the program.

It takes some time (4'52") so you might want to test it with a smaller example 81^9 where a solution exists as well.

Is the HP-48gx considered a CAS calculator? However I'm just using some functions from a library. Would it be fun to write these for an HP-35s? I guess it would be rather slow.

Thanks for posting the challenge.

Best regards

Thomas

Edited: 16 Apr 2010, 7:19 p.m. after one or more responses were posted


#58

Thomas, thanks for the post.

Quote:
Is the HP-48gx considered a CAS calculator?

I don't know, I'm not familiar with the 48gx's capabilities. Was it advertised as CAS? Did the term "CAS" even exist back in those days? I don't know. I think that the 50g is considered CAS, and isn't it a successor to the 48 series?

Nevertheless, please show the outputs of your program to identify the 9 prime numbers that sum to 1741^9. I think we all will be interested.


#59

The solution is the same as Hugh Steers already posted:

{
"16328505265216430302654575827"
"16328505265216430302654575887"
"16328505265216430302654576009"
"16328505265216430302654576091"
"16328505265216430302654576123"
"16328505265216430302654576291"
"16328505265216430302654576331"
"16328505265216430302654576333"
"16328505265216430302654576369"
}
#60

Google said the sum of first n prime is approx: s(n)~=1/2*n^2*ln(n)

We need the n from this equation: s(n+9)-s(n)=1741^9

It seems to me like an approximation of derivative of s(n):

ds/dn = (s(n+9)-s(n))/9 == 1741^9/9, so let's make derivative of s:
ds/dn = n*ln(n)+n/2 == 1741^9/9, this is equal:
(2*ln(n)+1)*n = 2*1741^9/9, solve this equation we get the n~=2.662E27

I have no idea about the number of known primes today, but I think this n is too large to determine the exact n for summing that nine primes...

(SRY 4 MY BAD ENGLISH)

#61

Here's a generalized solution for the 50g. It uses integer arithmetic and NEXTPRIME/PREVPRIME, so I'm cheating as far as the original challenge is concerned. Finds K consecutive primes that sum to N. No error checking on N and K.

On my 50g this found the answer in 6 minutes 53 seconds.


@ Program to figure if a given integer N is
@ the sum of K consecutive primes
@ Input:
@ Level 2: N
@ Level 1: K

@ Output:
@ Level 1: { list of primes } OR "NO ANSWER"

@ This works efficiently by realizing that the
@ K primes can't all be less than N/K, nor can
@ they all be greater.

« DUP2 IQUOT  N K pivot «
@ Get K primes that are less than pivot
{} pivot
1 K START
PREVPRIME
DUP ROT + SWAP
NEXT
DROP

@ You have a list of K primes on at level 1 now
@ add them up and while the sum is less than N,
@ remove the head (smallest) and add the next prime.
WHILE
DUP …LIST N <
REPEAT
DUP K GET @ Get last element
NEXTPRIME
SWAP TAIL SWAP +
END

@ Level 1 is now the answer or a list that's too large.
IF DUP …LIST N ‹ THEN
DROP "NO ANSWER"
END
»
»


#62

Thanks David.

I was going to ask Thomas Klemm if the 50g included the ALG library from the 48, but then your code shows that it is not necessary, I'm supposing here.

I appreciate this solution, and Thomas', for showing how this problem can be implemented using a very few lines of code. I've always appreciated that about RPL, but I've never actually taken the time to learn it myself. I love the simplicity of RPN, and the speed of RPN on the 30b.

I had hoped (and still hope, really) that the 30b and RPN might be able to solve this problem, but I imagine it will take repurposing, as Hugh has done with the Casio.

But maybe someone will surprize me!

Don


Possibly Related Threads...
Thread Author Replies Views Last Post
  RE: 35s sorting routine challenge - Gene's Challenge Miguel Toro 4 1,259 08-01-2007, 08:36 AM
Last Post: Miguel Toro

Forum Jump: