Challenge: Keith numbers « Next Oldest | Next Newest »

 ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 09-05-2009, 09:48 PM Number theory has all kinds of identifiers for mathematically unusual numbers. Take Keith numbers, for instance. I think it is easier to give an example of a Keith number than to explain mathematically what it is, so here goes. Is 14 a Keith number? Yes. Why? start a Fibonacci-like sequence with the individual digits of 14, and each subsequent number is the sum of the previous 2 (because 14 has 2 digits) numbers: 1,4,(1+4=)5, (4+5=)9, (5+9=)14. Since 14 is in the sequence that begins with 1,4, it is a Keith number. Is 30 a Keith number? No. Why? 3,0, (3+0=)3, (0+3=)3, (3+3=)6, (3+6=)9, (6+9=)15, (9+15=)24, (15+24)=39. Since 30 is not in the sequence, it is not a Keith number. What about 3 digit Keith numbers? Is 145 a Keith number? 1,4,5, (1+4+5=)10, (4+5+10=)19, (5+10+19=)34, (10+19+34=)63, (19+34+63=)116, (34+63+116=)213, so 145 is not a Keith number. So, the challenge is to write a calculator program (RPN, RPL, BASIC, pick your favorite language and calculator) to identify as many Keith numbers as you can. You can verify your results by Googling Keith number. And post your code so we can all benefit from your brilliance! I can't think of any practical reasons that Keith numbers are important, but there aren't that many of them and this problem does lend itself to solutions on the devices we have come to know and love. ▼ Valentin Albillo Posting Freak Posts: 1,755 Threads: 112 Joined: Jan 2005 09-05-2009, 11:36 PM Hi, Don: In the HP-71B, this 5-liner is as straightforward as it gets: ``` 1 DESTROY ALL @ OPTION BASE 1 @ DIM D(12) @ FOR N=10 TO 10^12-1 @ N\$=STR\$(N) 2 L=LEN(N\$) @ FOR I=1 TO L @ D(I)=VAL(N\$[I,I]) @ NEXT I 3 S=0 @ FOR I=1 TO L @ S=S+D(I) @ NEXT I @ IF S=N THEN DISP N ELSE IF S>N THEN 5 4 FOR I=1 TO L-1 @ D(I)=D(I+1) @ NEXT I @ D(L)=S @ GOTO 3 5 NEXT N >RUN 14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 31331 34285 34348 ... ``` It can be optimized in a number of ways, such as using MATH ROM statements and avoiding loops by just adding one value and subtracting another to keep the running sum instead of computing it in a loop, etc, etc, but what the heck ? The above code took less than 2 minutes to write, enter, and run, and it delivers the correct results, so ... Try to beat that time (from nothing to correct results) using RPL ... :-) Best regards from V. ``` ``` ▼ Keith Midson Senior Member Posts: 262 Threads: 52 Joined: Apr 2009 09-06-2009, 04:37 AM I like it for a whole lot of reasons ... Cheers, Keith Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 09-06-2009, 11:52 AM Thanks, V, great solution. I'm working on an RPN solution to run on the super-fast 12c to see what it can do with this problem. C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 09-07-2009, 05:08 AM Quote:Try to beat that time (from nothing to correct results) using RPL ... :-) Well, 2 mins is really a challange. Except if you are using the ISKEITH? binary function on your HP-28S which returns True(1) for any keith number k given as argument or False(0) otherwise. ```« DUP ->STR DUP SIZE -> k T n @ k-number, T is string representation, n is length « 1 n FOR i T i i SUB STR-> @ Put any digit of the k-number in the stack NEXT DO @ main loop performing sum of the n-digits n ROLL n DUPN 2 n START + NEXT @ compute the n-digits sum (additing n-1 times) SWAP DROP @ remove oldest digit from the stack UNTIL DUP k >= END @ loop until sum egals or overpasses k n ROLLD n 1 - DROPN @ remove remaining digts from stack, keeping last sum k == @ perform test: last sum of n-digits egal k ? » » 'ISKEITH?' STO ``` The ISKEITH? function/program may be used in any RPL calculator to list Keith's numbers; such as ```« 10 9999 FOR i IF i ISKEITH? THEN i PR1 END NEXT » 14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 ... ``` But, Don is right, a lot of optimisation have to be carry out to beat the oberall 2 mins delay :-) Especely with an HP-28S ! Edited: 7 Sept 2009, 2:29 p.m. after one or more responses were posted ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 09-07-2009, 09:58 AM C.Ret, thanks for your very elegant RPL solution to this problem. It "almost" makes me want to go out and buy a 50g and learn RPL. I had no idea that the 28s actually has an ISKEITH function, that is amazing. Great work. And thanks to Valentin for an equally elegant BASIC solution. Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 09-07-2009, 06:26 PM Oh, I think I see now, the 28s does NOT have a built-in ISKEITH function. You wrote it and called it ISKEITH, right? My understanding of RPL is not very advanced, I'm afraid. Yeah, when I did this problem in RPN, I knew I wanted to avoid moving the digits around the registers and adding all the digits to create the next entry each time, and the key was to figure out how to replace the un-needed number (after saving it so you can subtract it from the new sum) with the new sum during each cycle. And that worked fine, even with the 12c's limited indirect addressing. And in lines 26-29 I double the current sum and subtract the un-needed digit from the sum to get the new sum. It took a lot of thought and sheets of paper for me to get this to finally work, but it was worth it. I've thought about trying create a solution to this problem on the HP-65 or the 17bii+ solver, but the lack of indirect addressing killed that idea. C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 09-07-2009, 05:27 PM I was trying to convert the 5-liner HP-71B program from Valentin to an oldest Pocket whith a rudimental BASIC (such as a SHARP PC-1211) Quote:``` 1 DESTROY ALL @ OPTION BASE 1 @ DIM D(12) @ FOR N=10 TO 10^12-1 @ N\$=STR\$(N) 2 L=LEN(N\$) @ FOR I=1 TO L @ D(I)=VAL(N\$[I,I]) @ NEXT I 3 S=0 @ FOR I=1 TO L @ S=S+D(I) @ NEXT I @ IF S=N THEN DISP N ELSE IF S>N THEN 5 4 FOR I=1 TO L-1 @ D(I)=D(I+1) @ NEXT I @ D(L)=S @ GOTO 3 5 NEXT N ``` At first, string operation have to be avoid (not possible on a SHARP PC-1211). So mathematics have to be used in order to extract each digit from the N-number. Second, to compute the sum of the l-digits, manipulation and shifting of D(i+1) to D(i) can easely be avoid. At each step, the new sum of the last l-digits, which can be express as : `1 4 5(=1+4) 9(=4+5) 14(=5+9) 23(=9+14) ...` Each new term is egal to the double of the previous minus the droped digit : `1 4 5(=1+4) 9(=2*5-1) 14(=2*9-4) 23(=2*14-5) ...` This can spare the FOR/TO/NEXT loop computing the sum (see line 3) and D(i) transposition (line 4)! So, this is a second version of Valentin HP-71B program, which stil can be optimize : ``` 1 DESTROY ALL @ OPTION BASE 1 @ DIM D(99) @ FOR N=10 TO 99999 2 S=0 @ L=1+INT(LOG(N)) @ FOR I=1 TO L @ B=10^(L-I) @ D(I)=INT(N/B) MOD 10 @ S=S+D(I) @ NEXT I @ I=L 3 IF S k n @ k tested number, n number of digits « 0 @ initiate sum S=0 1 n FOR i k n i - ALOG / IP 10 MOD @ put i-digit into stack SWAP OVER + @ add it to sum NEXT WHILE DUP k < @ loop while sum is less than k REPEAT n 1 + ROLL OVER 2 * SWAP - @ new sum is 2x last sum minus least i-digit END n 1 + ROLLD n DROPN @ save sum and remove remaining digits k == @ test sum is k » » 'ISKEITH?' STO ``` These three program are still relatively slow to list all Keith number since most of the running time is used to test any N sequnetially. We are still waiting for a clever way to pick up keith-numbers ! ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 09-07-2009, 05:49 PM Quote: We are still waiting for a clever way to pick up keith-numbers ! You'll probably be waiting for sometime. I've looked into this on/off throughout the 3-day US holiday weekend and AFAIK the only known method is by exhaustive search. It'd be nice to find a way to eliminate a candidate sooner than later. Of course, I have not done an exhaustive search myself for a better solution. It's been a lazy weekend. There are reverse Keith numbers as well, e.g. 341 following the same logic ends up as 143. ▼ Pal G. Senior Member Posts: 260 Threads: 21 Joined: Nov 2006 09-08-2009, 10:41 AM Per Wolfram Mathworld: ```"There is no known general technique for finding Keith numbers except by exhaustive search. ``` Valentin Albillo Posting Freak Posts: 1,755 Threads: 112 Joined: Jan 2005 09-08-2009, 09:17 AM Hi, C. Ret: Thanks for your interest in my instant-coffee HP-71B solution, but be aware that in your HP-71B version you've used LOG (base e-logarithm) when you actually want to use LGT (decimal logarithm) so your HP-71B version as written is faulty. Also, in the HP-71B you can use N DIV B instead of INT(N/B) to perform integer division, etc. Not so in the PC-1211 BASIC dialect, which lacks DIV. Best regards from V. Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 09-07-2009, 02:12 AM Well, after considerable frustration with the 12c+ indirect addressing via the cfj command and a nasty bug that took hours to track down, here is a solution for the 12c. Enter the number you want to start with, like 10, and press R/S. It will run until you stop it, and it will display each Keith number and pause for 1 second. If you have an original 12c, it will take a rather long time. If you have the new 12c+ (Arm-based processor), it will go considerably faster. And if you have the 12c Windows-based emulator that HP is selling for \$20, it will go faster still (although the original version would not handle the pse command correctly, but they sent me a fix for that). Here is the code. I used all 5 TVM variables for purposes for which they were not intended. ```01 clr fin 02 cf0 03 1 04 0 05 / 06 i 07 frac 08 1 09 0 10 x 11 cfj 12 rcl pv 13 + 14 pv 15 rcl i 16 intg 17 x=0 18 goto 20 19 goto 03 20 rcl n 21 fv 22 rcl cfj 23 pmt 24 rcl pv 25 cfj 26 2 27 x 28 rcl pmt 29 - 30 pv 31 rcl n 32 1 33 - 34 n 35 x=0 36 goto 38 37 goto 40 38 rcl fv 39 n 40 rcl pv 41 rcl 0 42 - 43 x=0 44 goto 46 45 goto 49 46 rcl 0 47 pse 48 goto 54 49 rcl pv 50 rcl 0 51 x<=y 52 goto 54 53 goto 22 54 rcl 0 55 1 56 + 57 goto 01 ``` Crawl Senior Member Posts: 306 Threads: 3 Joined: Sep 2009 09-08-2009, 07:38 AM Fun! I haven't done one of these in a while. The gist of this program is that first the initial number's digits, then the running sums, are stored as entries in a row matrix. You put the number D on the stack, and it exhaustively searches for all Keith numbers with D digits. So, on a real HP50g, if you put 2 on the stack and run the program, you get (after about a minute) ```14 19 28 47 61 75 ``` You might want to run it on an emulator for much larger values of D! ```%%HP: T(3)A(R)F(.); \<< 0 0 0 0 \-> D S N J M \<< 10 D 1 - ^ 1 + 10 D ^ 1 - FOR N N \->STR 'S' STO 1 D FOR J S J J SUB OBJ\-> NEXT D ROW\-> 'M' STO DO 2 D FOR J M J GET NEXT M 1 GET 2 D FOR J M J GET + NEXT D ROW\-> 'M' STO UNTIL M D GET N \>= END M D GET N == IF THEN N END NEXT \>> \>> ``` ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 09-08-2009, 12:16 PM Thanks for another great RPL solution to this problem.

 Possibly Related Threads... Thread Author Replies Views Last Post HP Prime: complex numbers in CAS. Alberto Candel 1 1,406 12-06-2013, 02:36 PM Last Post: parisse [HP Prime] Plots containing complex numbers bug? Chris Pem10 7 2,859 12-05-2013, 07:40 AM Last Post: cyrille de Brébisson comparing numbers on the WP 34S Kiyoshi Akima 7 1,993 10-19-2013, 09:28 AM Last Post: walter b HP Prime: Operations with Large Numbers Eddie W. Shore 0 763 10-19-2013, 12:24 AM Last Post: Eddie W. Shore HHC 2013 room numbers David Hayden 2 1,036 09-20-2013, 05:34 PM Last Post: sjthomas [HP-Prime xcas] operations with complex numbers + BUGs + Request CompSystems 9 2,868 09-08-2013, 10:40 PM Last Post: CompSystems TED Talk: Adam Spencer: Why I fell in love with monster prime numbers Les Bell 3 1,405 09-05-2013, 12:54 PM Last Post: Ken Shaw Irrationality in numbers....the book Matt Agajanian 4 1,498 08-30-2013, 04:14 PM Last Post: Matt Agajanian Best HP calculator for crunching numbers rpn fan 51 9,647 08-05-2013, 03:17 PM Last Post: rpn fan HP 50G List of Library numbers already in use? Michael Lopez 2 983 08-04-2013, 10:10 PM Last Post: Michael Lopez

Forum Jump: