challenge « Next Oldest | Next Newest »

 ▼ Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-15-2010, 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. ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 04-15-2010, 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` There must be a short cut... - Pauli ▼ Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-15-2010, 07:35 PM I'm hoping someone can dazzle us. ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 04-15-2010, 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 Han Unregistered Posts: 709 Threads: 104 Joined: Nov 2005 04-15-2010, 10:19 PM 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). ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 04-15-2010, 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. - Pauli ▼ Egan Ford Unregistered Posts: 1,619 Threads: 147 Joined: May 2006 04-15-2010, 11:58 PM Not to give too much away. But 5 are below and 4 above. ▼ hugh steers Unregistered Posts: 536 Threads: 56 Joined: Jul 2005 04-16-2010, 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 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. ▼ Egan Ford Unregistered Posts: 1,619 Threads: 147 Joined: May 2006 04-16-2010, 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}] ``` ▼ hugh steers Unregistered Posts: 536 Threads: 56 Joined: Jul 2005 04-16-2010, 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? ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 04-16-2010, 04:06 PM 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 ▼ Bart (UK) Unregistered Posts: 850 Threads: 10 Joined: Mar 2009 04-16-2010, 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 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. ▼ hugh steers Unregistered Posts: 536 Threads: 56 Joined: Jul 2005 04-16-2010, 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), 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. ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 04-17-2010, 01:22 AM 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 ▼ hugh steers Unregistered Posts: 536 Threads: 56 Joined: Jul 2005 04-17-2010, 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! ▼ Katie Wasserman Unregistered Posts: 1,477 Threads: 71 Joined: Jan 2005 04-17-2010, 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 ▼ Glenn Shields Unregistered Posts: 63 Threads: 8 Joined: Dec 2009 04-19-2010, 09:40 PM 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. :-) Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-17-2010, 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 Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-17-2010, 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 1632.....140+1/9 response np(x) 1632.....140+1/9 same response?? I expected 1632....576291 ``` ▼ hugh steers Unregistered Posts: 536 Threads: 56 Joined: Jul 2005 04-17-2010, 11:41 AM 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. ▼ Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-17-2010, 04:33 PM Thanks, Hugh, I'll try that. Don Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 04-16-2010, 05:51 PM 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 C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 04-16-2010, 04:28 PM 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 ? ▼ Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-16-2010, 05:03 PM 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? ▼ hugh steers Unregistered Posts: 536 Threads: 56 Joined: Jul 2005 04-17-2010, 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 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 :-) Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 04-16-2010, 06:57 PM 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 Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 04-16-2010, 06:30 PM 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 ▼ Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-16-2010, 07:16 PM 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. ▼ Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 04-16-2010, 07:25 PM The solution is the same as Hugh Steers already posted: ```{ "16328505265216430302654575827" "16328505265216430302654575887" "16328505265216430302654576009" "16328505265216430302654576091" "16328505265216430302654576123" "16328505265216430302654576291" "16328505265216430302654576331" "16328505265216430302654576333" "16328505265216430302654576369" } ``` Csaba Tizedes (Hungary) Unregistered Posts: 59 Threads: 9 Joined: Apr 2008 04-16-2010, 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: 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) David Hayden Unregistered Posts: 528 Threads: 40 Joined: Dec 2008 04-16-2010, 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 @ 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 » » ``` ▼ Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 04-17-2010, 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

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

Forum Jump: