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.
challenge

04152010, 07:05 PM
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.
04152010, 07:18 PM
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
04152010, 07:35 PM
I'm hoping someone can dazzle us.
04152010, 07:38 PM
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
04152010, 10:19 PM
Quote: 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).
04152010, 10:48 PM
Actually they are around that number, the primes are consecutive which means they must lie around about the target number over nine.
04152010, 11:58 PM
Not to give too much away. But 5 are below and 4 above.
04162010, 09:23 AM
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 Pk, where P prime greater than k and smaller than k, say 7 each way. i get:
Pk, P > k need to find a combination of the above that sum to 1, so that sum (Pk_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+2291749131313253 = 1 so the desired numbers are k with each of these added.
16328505265216430302654576291 it was a bit lucky that the ones immediately up and down were the answers.
Edited: 16 Apr 2010, 9:25 a.m.
04162010, 11:48 AM
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}]
04162010, 12:51 PM
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?
04162010, 04:06 PM
Quote: Which one, a 50g? Don stated the challenge so as to not use a CAS calculator. This would require writing some 30digit math routines and programing a probabilistic primality test routine using them. That is, unless there's some really clever short cut. Katie
04162010, 04:28 PM
Quote: OK.
1741^9 is about 1.4696E29 on my HP28S. I win the cahllenge ?
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 weekend ?
04162010, 05:03 PM
Quote: I don't know if it actually can be solved on a nonCAS 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 repurposing 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?
04162010, 05:51 PM
Quote: 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
04162010, 06:21 PM
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 fx9860G/Gii (listed as nonCAS) 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.
04162010, 06:30 PM
Here's a program for an HP48gx with the ALGlibrary installed:
\<< \> n 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 HP48gx considered a CAS calculator? However I'm just using some functions from a library. Would it be fun to write these for an HP35s? I guess it would be rather slow. Thanks for posting the challenge.
Best regards Edited: 16 Apr 2010, 7:19 p.m. after one or more responses were posted
04162010, 06:49 PM
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: 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)
04162010, 06:57 PM
The ALG48.LIB is about 50K. I'm afraid it won't fit into your HP28s. 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. MillerRabin) will take 21 minutes for 9999999967 even on a 28s.
Cheers
04162010, 07:16 PM
Thomas, thanks for the post.
Quote: 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.
04162010, 07:25 PM
The solution is the same as Hugh Steers already posted:
{
04162010, 09:11 PM
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
04162010, 10:01 PM
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), n1) 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. 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, try these
a=1741^91
04172010, 01:22 AM
Hugh, I just downloaded your new code, very nice and fast! But I tired:
x=9999999967^2 and while prime(x) returned 0, fac(x) returned 99999999340000001089. I was expecting 9999999967. Is that wrong? Katie
04172010, 02:01 AM
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
04172010, 02:10 AM
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
04172010, 08:44 AM
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!
04172010, 08:57 AM
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 homebrew 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 :)
04172010, 10:28 AM
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
04172010, 11:41 AM
it wont touch the number if its not an integer. try,
1741^91 then
np(ans) keep doing this for a list of the primes, then repeat with pp(n) for the previous primes.
04172010, 12:22 PM
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
04172010, 04:33 PM
Thanks, Hugh, I'll try that. Don
04192010, 09:40 PM
Thanks for that bug, it's interesting that ISITPRIME says 0. and 
« Next Oldest  Next Newest »

Possibly Related Threads…  
Thread  Author  Replies  Views  Last Post  
RE: 35s sorting routine challenge  Gene's Challenge  Miguel Toro  4  1,569 
08012007, 08:36 AM Last Post: Miguel Toro 