Short & Sweet Math Challenges #6 « Next Oldest | Next Newest »

 ▼ Ex-PPC member Member Posts: 142 Threads: 24 Joined: Jan 1970 03-03-2003, 07:11 AM Just to light up a little this week, here's a new Short & Sweet Math Challenge (tm), for you to try on your favorite HP calc [NOT-NOT-NOT on your PC and/or Mac, that's NOT the point :-) ] The Challenge Find a 10-digit integer number ABCDEFGHIJ where all its digits A,B,...,J must be different, such that A is divisible by 1, AB is divisible by 2, ABC is divisible by 3, and so on. For instance, 1234567890 isn't a solution, because 1 is divisible by 1, 12 is divisible by 2, and 123 is divisible by 3, but 1234 is *not* divisible by 4. Requirements You may try it in any HP programmable calculator; the shortest and more elegant the program (within the selected model's capabilities, of course), the better. Solutions and Generalization Next week I'll provide a short program for the HP-71B that solves this challenge, as well as another program to solve the more generalized challenge of finding all numbers N, from 1-digit numbers onwards, allowing for repeated digits, that have the property that their first M-digits (from the left) form a number divisible by M (for instance, 123 would be such a solution for M=3, but 1234 wouldn't for M=4). If you would like to tackle this generalized challenge, try to write a short program which will find and optionally print out solutions, and see if you can stablish whether there are a finite or infinite number of solutions, and in the former case what's the maximum value for M, and how many solutions are there having 1,2,..., M digits. ▼ Patrick Senior Member Posts: 266 Threads: 32 Joined: Jan 1970 03-04-2003, 02:34 PM Here is my "first" solution. I've tried to use only features common to a bunch of HP programmables (e.g., didn't use MOD function, no recall arithmetic). This works almost verbatim on my HP-12C for example, which has one of the simpler programming models. I haven't thought about it too hard yet, but I think this program produces the smallest number having the desired properties: 1,020,005,640. BTW, the innocent looking subtraction in step 010 is, I think, critical to this algorithm working for all ten digits. Otherwise, it works only up to 9 digits. Change the number in step 2 to one less than the number of digits to produce. In this version, I used 9 to produce a 10 digit result. Alternatively, have the number of digits you want in the X register when the program starts and replace the first two steps by the three steps 1, -, 10^x. 001 EEX 002 9 003 ENTER 004 1 005 STO 0 006 10 007 * 008 1 009 STO + 0 010 - 011 RCL 0 012 + 013 LAST X 014 / 015 INT 016 RCL 0 017 * 018 x<=y? (can substitute x J must be equal to 0 So the problem is now for ABCDEFGHI. For ABCDE to be divisible by 5 => E must be equal to 5 Now for the reason of odd and even numbers : A,C,G,I are in {1,3,7,9} ....and B,D,F,H are in {2,4,6,8} So we must have 4!*4! combinations : 576 possibilities This is my very little contribution....... PS : I really like these S&SMCs ... but my old brain is really tired. Michael F. Coyle Member Posts: 172 Threads: 5 Joined: Jan 1970 03-11-2003, 05:18 PM I know it's kind of late in the game, but I do have a solution to this problem, written for the 48GX. I have to leave in a few minutes so I don't have time to post the code but I will send it to anyone interested. A brief description follows. It solves the more general problem of finding all of the 1, 2, 3, ..., 10 digit numbers with the required properties (first N digits divisible by N, no repeated digits). It starts with a list of all the valid one-digit answers (1..9). For each of these, it forms trial 2-digit numbers by tacking on each of the digits 0..9 and seeing if the resulting 2-digit number meets the criteria; if so, it is added to a list of 2-digit solutions. This is then repeated with the 2-digit numbers to get 3-digit solutions, and so on. This is all done in a big loop, of course. (CS fans will recognize this as a "breadth-first search.") The program takes about 25 minutes to run and produces a list of 10 lists, giving all the solutions. The number of solutions for each size number starts at 9 for one digit and increases to 220 for 5-digit numbers and then decreases down to just one 10-digit answer. (I will not include it here in case anyone else is still working on it.) I manually verified that the 10-digit answer and its smaller prefixes met both criteria. Hopefully this will still be of interest to someone. For me, the fun was just getting a working program. ▼ Ex-PPC member Member Posts: 142 Threads: 24 Joined: Jan 1970 03-13-2003, 06:37 AM Michael wrote: I know it's kind of late in the game, but I do have a solution to this problem, written for the 48GX [...] Hopefully this will still be of interest to someone. For me, the fun was just getting a working program. Thanks for your interest in my challenge, perhaps it was a little more difficult than the usual "do this simple thing in the least possible number of programming steps", but it certainly offered an opportunity to show off one's favorite HP calc and some advanced programming techniques, right ? As promised, here's a solution to both the original and the extended challenge, for the HP-71B. As usual, it's far from optimal, but it can be written very easily and gets the job done quickly: This short (164 bytes) program recursively finds all numbers that have the property that the number consisting in the first N leftmost digits is divisible by N, for N ranging from 2 to 9 digits. Repeated digits are allowed for this version. ```10 DESTROY ALL @ OPTION BASE 0 @ DELAY 0,0 @ STD 20 FOR I=1 TO 9 @ CALL TST((I),2,9) @ NEXT I @ DISP "DONE!" @ END 30 SUB TST(N,D,M) @ N=10*N @ FOR I=0 TO 9 @ X=N+I @ IF MOD(X,D) THEN 50 40 DISP D;X @ IF D#M THEN CALL TST(X,D+1,M) 50 NEXT I @ END SUB ``` It simply starts from 1-digit numbers and calls a subprogram that adds a new digit, testing all 10 possibilities for divisibility. When a suitable candidate appears, the subprogram calls itself, to add yet another digit, and so on till the number is 9 digits long and all possibilities have been tested. Brief comments: Line 10 simply sets up some initial conditions; you may want to change the DELAY to slow down the display, but the STD is important to keep the presentation tidy. Line 20 is the "main program": it just stablishes a loop to find solutions from 2 to 9 digits long, and calls the subprogram to do the actual work. That's it. You could search for numbers up to 12 digits long just by changing the 9 to 12 ! Line 30 is the subprogram: it tests all 10 possibilities by adding a new digit to the already existing ones, and if the divisibility condition is met, it simply calls itself to add yet another digit Notice how the recursive call CALL TST(X,D+1,M) at line 40 depends on a condition, else the recursion would go ever deeper. If you RUN this program, you'll get an output like this: 2 10 -> 3 102 -> 4 -> 1020 -> 5 -> 10200 -> 6 102000 -> 7 1020005 -> 8 10200056 -> 9 -> 102000564 -> 6 102006, etc To find a 10-digit solution with no repeated digits, as the original challenged asked for, first we notice that for a 10-digit number to be divisible by 10, it must end in 0. So we just need to find 9-digits solutions, 0 excluded, then add a final 0 to all of them. We just need a very few changes to the program above, like this 200+ byte version: ```10 DESTROY ALL @ OPTION BASE 0 @ DELAY 0,0 @ STD 20 FOR I=1 TO 9 @ CALL TST((I),2,9) @ NEXT I @ DISP "DONE!" @ END 30 SUB TST(N,D,M) @ N=10*N @ FOR I=1 TO 9 @ X=N+I @ IF MOD(X,D) THEN 50 32 A\$=STR\$(X) @ FOR J=1 TO LEN(A\$) @ IF POS(A\$[J+1],A\$[J,J]) THEN 50 34 NEXT J 40 DISP D;X @ IF D#M THEN CALL TST(X,D+1,M) 50 NEXT I @ END SUB ``` As before, line 10 sets things up, but STD is even more mandatory, for the STR\$ conversion below. The loop at line 30 in the subprogram begins at 1 instead of 0, as 0 must be the final, 10th digit. Lines 32 and 34 simply check for repeated digits, by converting the candidate number (which already meets the divisibility requirement) to a string, then using the POS function to find if any character occurs more than once. It's a simple, non-optimal idea that works. The rest of the program is just the same. When RUN, it outputs: 2 12 -> 3 123 -> ... -> 9 381654729 and so, the one and only 10-digit solution is 3816547290. That's all, hope you enjoyed it, and see how recursion makes an easy job of apparently complex tasks.

 Possibly Related Threads... Thread Author Replies Views Last Post Need help understanding math.... cyrille de Brébisson 9 1,670 12-13-2013, 02:23 AM Last Post: Didier Lachieze HP Prime - Short "learning" modules CR Haeger 1 623 11-27-2013, 02:13 PM Last Post: Jonathan Cameron I have written a short introduction to the HP Prime Michael Carey 7 1,275 11-18-2013, 08:04 PM Last Post: Michael Carey HP-65 short circuit Ignacio Sánchez 2 708 10-22-2013, 08:27 AM Last Post: Ignacio Sánchez Reig OT: a math competition site Pier Aiello 0 477 09-16-2013, 06:03 AM Last Post: Pier Aiello Simple Math Question Namir 2 626 08-09-2013, 06:13 PM Last Post: Eddie W. Shore Cool math clock Bruce Bergman 28 3,006 04-10-2013, 03:13 AM Last Post: Siegfried (Austria) FRAM71 for HP-71B, short update #3 Hans Brueggemann 15 1,701 01-20-2013, 10:22 AM Last Post: Jerry Raia Math Challenge I could not solve Meindert Kuipers 22 2,544 01-05-2013, 04:43 PM Last Post: Thomas Klemm Math Question Namir 0 406 11-06-2012, 07:43 AM Last Post: Namir

Forum Jump: