The Museum of HP Calculators

HP Forum Archive 19

Mini-Challenge: Zip Code
Message #1 Posted by Thomas Klemm on 23 Sept 2010, 4:52 p.m.

The following challenge is based on an arithmetic problem I found in a mathematics book for elementary school. Contrary to other countries we use only a four digit zip code in Switzerland.

These are the steps necessary to create the next zip code:

1. Select the zip code of a Swiss location.
2. Compose the maximum number of the four digits.
3. Compose the smallest possible number of the four digits.
4. Calculate the difference.

## Example

2. The maximum number made of these four digits is: 5431
3. The minimal number made of these four digits is: 1345
4. The difference is: 5431 - 1345 = 4086

## Analysis

Write a program for the HP calculator of your choice that returns the next zip code. What is the behavior if you iterate this? Make a speculation.

## Proof

Try to proof your assumption. Can your calculator be of any help?

## Solution

I will add my solution for the HP-15C here within a couple of days.

Hope you have as much fun as I had.
Thomas

PS: And where will all this lead us?

 Re: Mini-Challenge: Zip CodeMessage #2 Posted by Chuck on 24 Sept 2010, 12:33 a.m.,in response to message #1 by Thomas Klemm Question: does it always require to be four digits. That is will a zip of 12 (or 0012) transition to 2100-0012 = 2088 If so, I'm getting just about nothing but cycles. Sadly I'm not using an HP, though. CHUCK

 Re: Mini-Challenge: Zip CodeMessage #3 Posted by Thomas Klemm on 24 Sept 2010, 2:30 a.m.,in response to message #2 by Chuck Quote: That is will a zip of 12 (or 0012) transition to 2100-0012 = 2088 The authors of the book don't mention this special case but I did the same as you: add leading zeros whenever needed to get a four digit number. Quote: Sadly I'm not using an HP, though. At least to me that was part of the fun. Best regards Thomas

 Re: Mini-Challenge: Zip CodeMessage #4 Posted by Chuck on 24 Sept 2010, 10:23 a.m.,in response to message #2 by Chuck Aack. Egg on my face. It was too late last night and I forgot the "make the smallest" and "make the largest" number part. (I was just reversing the original number, doh.) Should be any easy fix with my program.

 Re: Mini-Challenge: Zip CodeMessage #5 Posted by Thomas Klemm on 27 Sept 2010, 2:05 p.m.,in response to message #2 by Chuck It appears that Wikipedia and MathWorld (or rather Sloane) disagree on the values that will lead to 0. Wikipedia: Quote: The only four-digit numbers for which Kaprekar's routine does not reach 6174 are repdigits such as 1111, which give the result 0 after a single iteration. All other four-digits numbers eventually reach 6174 if leading zeros are used to keep the number of digits at 4: ``` 2111  1112 = 0999 9990  0999 = 8991 (rather than 999  999 = 0) ``` MathWorld: Quote: Exactly 77 4-digit numbers, namely 1000, 1011, 1101, 1110, 1111, 1112, 1121, 1211, ... (Sloane's A069746), reach 0. The question is whether 999/0999 is considered a 3- or a 4-digit number. As I didn't read Kaprekar's original paper I don't know which position is correct. However the Online Kaprekar script returns: ```9990 - 0999 = 8991 9981 - 1899 = 8082 8820 - 0288 = 8532 8532 - 2358 = 6174 ``` After all this your question seems fairly reasonable. Best regards Thomas

 Re: Mini-Challenge: Zip CodeMessage #6 Posted by Dave Shaffer (Arizona) on 24 Sept 2010, 12:35 a.m.,in response to message #1 by Thomas Klemm Quote:Write a program for the HP calculator of your choice that returns the next zip code I pretended I had a 71B (which I don't) and wrote a BASIC program. I won't give too much away, but it does converge (fairly quickly), but not to anything I might have guessed. If you have ZIP codes which have 4 digits of the same value, such as 5555, it converges/collapses very quickly of course, to 0000.

 Re: Mini-Challenge: Zip CodeMessage #7 Posted by Thomas Klemm on 24 Sept 2010, 2:39 a.m.,in response to message #6 by Dave Shaffer (Arizona) The only possible Swiss ZIP codes made of the same digits are: 4444 Rümlingen 8888 Heiligkreuz Best regards Thomas

 Re: Mini-Challenge: Zip CodeMessage #8 Posted by Paul Dale on 24 Sept 2010, 3:07 a.m.,in response to message #1 by Thomas Klemm Warning a spoiler ahead.... Read at own risk.... I really really meant that.... Turn back if you don't want it spoiled.... Australia also uses four digit postal (ZIP) codes.... It leads to one of my favourite mathematical results: Kaprekar's constant. Also true for three digit zip codes I believe. Sorry no program from me :-( - Pauli

 Re: Mini-Challenge: Zip CodeMessage #9 Posted by Patrice on 24 Sept 2010, 6:05 a.m.,in response to message #8 by Paul Dale Quote: Kaprekar's constant One of my favorite too, and already fun with just a paper and a pen ! Patrice

 Re: Mini-Challenge: Zip CodeMessage #10 Posted by Dave Shaffer (Arizona) on 24 Sept 2010, 12:27 p.m.,in response to message #8 by Paul Dale Quote:Kaprekar's constant I didn't know that is what it is called, but my little BASIC program did converge to the right value. (Patrice - bonjour. Did you get to Arches Park?)

 Re: Mini-Challenge: Zip Code - Casio fx-5800PMessage #11 Posted by Marcus von Cube, Germany on 24 Sept 2010, 1:02 p.m.,in response to message #1 by Thomas Klemm Programming the Casio isn't as funny as it could be, but finally, I've arrived: '->' is a single char, entered with STO, indentation and comments added for humans. ```4->N:?N: '# of digits Lbl 1:"NUMBER"?Z: 'ask for number, show last result 0->DimZ:N->DimZ 'create (and clear) Z[1]..Z[N] For 1->I To N: 'cut number in N digits Z-Int(Z/10)x10->A: 'get right most digit For 1->J To N: 'find proper place for digit If Z[J]B:Z[J]->A: 'stored digit is smaller B->Z[J]: 'swap with current digit IfEnd: Next: Next: 0->A:0->B: 'A is high number, B low number For 1->I To N: 'A,B construction loop Ax10+Z[I]->A: 'shift A and add next digit to the right Bx10+Z[N+1-I]->B: 'same as above but in reverse digit order Next: A-B->Z: 'new number Z as difference of A and B Cls:"\ \ 'press EXE twice ": 'clear screen and position cursor Locate 1,1," ": Locate 1,2," ": 'remove unwanted control chars on screen Locate 17-N,1,A: Locate 17-N,2,B: 'show both numbers Goto 1 'show (and get new) number ``` It's a bit clumsy to produce a nice screen display with this calculator, because 'Locate' does not position the cursor for the next input statement and the EXE key leaves an arrow symbol on the screen. Edited for typo in code. Edited: 26 Sept 2010, 2:03 p.m.

 Re: Mini-Challenge: Zip CodeMessage #12 Posted by George Litauszky on 26 Sept 2010, 4:54 a.m.,in response to message #1 by Thomas Klemm Hi Thomas and hi everybody! This is a simple HP 50g solution for your challenge. My stack diagram is: (Level(n), Level(n-1), ...Level(1)) Prg ZCODE: Input: 1432 ; For example ``` DUP (1432, 1432) ; Save input for comparsion 1 3 FOR N 10 IDIV2 SWAP NEXT (1432, 2, 3, 4, 1) ; The order isn't significant. 4 ->LIST (1432, {2 3 4 1}) SORT (1432, {1 2 3 4}) DUP (1432, {1 2 3 4}, {1 2 3 4}) REVLIST (1432, {1 2 3 4}, {4 3 2 1}) EVAL (1432, {1 2 3 4}, 4, 3, 2, 1) NBUILD (1432, {1 2 3 4}, 4321) ; See below. SWAP (1432, 4321, {1 2 3 4}) EVAL NBUILD (1432, 4321, 1234) - (1432, 3087) ; The input and the first result. ``` Prg NBUILD: Input: (1, 2, 3, 4) ``` 1 3 FOR N SWAP (1, 2, 4, 3) 10 N ^ (1, 2, 4, 3, 10) ;If N= 1 then 10^1= 10 * (1, 2, 4, 30) + (1, 2, 34) NEXT ``` The result: The Kaprekar's constant after some iterations. Hungary also uses four digit postal (ZIP) codes. George Edited: 26 Sept 2010, 4:59 a.m.

 Re: Mini-Challenge: Zip CodeMessage #13 Posted by Mark Storkamp on 27 Sept 2010, 9:35 a.m.,in response to message #1 by Thomas Klemm And here's a 41 solution. Start with number in the x register, and returns results in the x register ``` 01 LBL "ZIP"  02 FIX 04  03 1 E4  04 /  05 CLA 'Puts the number in Alpha register  06 ARCL X ' to decompose it onto the stack  07 ATOX  08 ATOX  09 ATOX  10 48  11 -  12 STO 01  13 ATOX  14 48  15 -  16 ATOX  17 48  18 -  19 ATOX  20 48  21 -  22 RCL 01  23 X<=Y? 'Bubble sort the values on the stack  24 X<>Y  25 RDN  26 X<=Y?  27 X<>Y  28 RDN  29 X<=Y?  30 X<>Y  31 RDN  32 RDN  33 X<=Y?  34 X<>Y  35 RDN  36 X<=Y?  37 X<>Y  38 R^  39 X<=Y?  40 X<>Y  41 STO 04 'Store the digits in 01 thru 04  42 RDN  43 STO 03  44 RDN  45 STO 02  46 RDN  47 STO 01  48 RCL 04 'Recombine the digits...  49 1 E3 ' Probably room for some optimizations  50 * ' here using the stack better  51 +  52 RCL 03  53 1 E2  54 *  55 +  56 RCL 02  57 1 E1  58 *  59 +  60 RCL 01  61 1 E3  62 *  63 RCL 02  64 1 E2  65 *  66 +  67 RCL 03  68 1 E1  69 *  70 +  71 RCL 04  72 +  73 - ' and find the difference  74 END ```

 Re: Mini-Challenge: Zip CodeMessage #14 Posted by Mark Storkamp on 27 Sept 2010, 4:21 p.m.,in response to message #13 by Mark Storkamp Thomas Klemm wrote: Quote: I know it wasn't a hard problem but still an occasion to use your best loved machines. Nevertheless I hope you enjoyed the contest. It's the easier challenges that I'm more likely to attempt, and I always seem to learn some new trick by trying it. For example, by stealing liberally from Thomas's 15C code I was able to shorten mine considerably and also eliminate use of any registers. ``` 01 LBL "ZIP2"  02 1 E4  03 /  04 XEQ 01  05 XEQ 01  06 XEQ 01  07 STO L 'Maybe I went to too extreme lengths to  08 CLX ' eliminate any registers  09 10  10 ST* L  11 CLX  12 RCL L  13 X>Y? 'Slightly improved sorting code from Thomas's code  14 X<>Y  15 RDN  16 X>Y?  17 X<>Y  18 RDN  19 X>Y?  20 X<>Y  21 R^  22 X>Y?  23 X<>Y  24 R^  25 X>Y?  26 X<>Y  27 RDN  28 X>Y?  29 X<>Y 'Here's where I'm most disappointed at not  30 - ' figuring out the answer was 999(d-a)+90(c-b)  31 90  32 *  33 X<>Y  34 R^  35 -  36 999  37 *  38 +  39 RTN  40 LBL 01  41 10  42 *  43 INT  44 LASTX  45 FRC  46 RTN  47 END ```

 Re: Mini-Challenge: Zip CodeMessage #15 Posted by Thomas Klemm on 28 Sept 2010, 11:34 a.m.,in response to message #14 by Mark Storkamp Hi Mark You could remove line 46 RTN as the following line 47 END does the same. I also tested your idea of dividing the entry first by 103: ```001 LBL A 002 EEX 003 3 004 ÷ 005 GSB 0 006 GSB 0 007 GSB 0 (...) 038 LBL 0 039 INT 040 LASTx 041 FRAC 042 RCL × 0 043 RTN ``` It uses the same amount of bytes, is one line longer and might be a little faster. However entering numbers is usually rather slow. So I'm not sure. Cheers Thomas

 Re: Mini-Challenge: Zip CodeMessage #16 Posted by Mark Storkamp on 28 Sept 2010, 4:18 p.m.,in response to message #15 by Thomas Klemm I don't have RCL arithmetic at my disposal, and in a first quick go at it I couldn't get the number decomposed without using a register unless I divided by 1E4 first. That way I was left with integers for all but the final digit. I could probably redo it now without the divide if I ended up with 0 - 0.9 on the stack, and used 9990(d-a)+900(c-b). And the last CLX RCL L could be replaced with an X<>L. But I'm not sure if all 41s could do that, or only the CX.

 Re: Mini-Challenge: Zip CodeMessage #17 Posted by Thomas Klemm on 29 Sept 2010, 10:56 a.m.,in response to message #16 by Mark Storkamp Quote: I don't have RCL arithmetic at my disposal One of the reasons why I chose HP-15C. Quote: And the last CLX RCL L could be replaced with an X<>L. Yes, it can: ``` 01 LBL "6174" 02 E3 03 / 04 XEQ 01 05 XEQ 01 06 XEQ 01 07 X>Y? 08 X<>Y 09 RDN 10 X>Y? 11 X<>Y 12 RDN 13 X>Y? 14 X<>Y 15 R^ 16 X>Y? 17 X<>Y 18 R^ 19 X>Y? 20 X<>Y 21 RDN 22 X>Y? 23 X<>Y 24 - 25 90 26 * 27 X<>Y 28 R^ 29 - 30 999 31 * 32 + 33 RTN 34 LBL 01 35 INT 36 ST- L 37 10 38 ST* L 39 X<> L 40 END ```

 Re: Mini-Challenge: Zip CodeMessage #18 Posted by Thomas Klemm on 27 Sept 2010, 2:59 p.m.,in response to message #1 by Thomas Klemm Quote: The following challenge is based on an arithmetic problem I found in a mathematics book for elementary school. Quote: I will add my solution for the HP-15C here within a couple of days. Initialization: ```10 STO 0 ``` ```001 - 42,21,11 LBL A 022 - 30 - 002 - 32 0 GSB 0 023 - 9 9 003 - 32 0 GSB 0 024 - 0 0 004 - 32 0 GSB 0 025 - 20 × 005 - 43,30, 7 TEST 7 026 - 34 x<>y 006 - 34 x<>y 027 - 43 33 R-^ 007 - 33 R-v 028 - 30 - 008 - 43,30, 7 TEST 7 029 - 9 9 009 - 34 x<>y 030 - 9 9 010 - 33 R-v 031 - 9 9 011 - 43,30, 7 TEST 7 032 - 20 × 012 - 34 x<>y 033 - 40 + 013 - 43 33 R-^ 034 - 43 32 RTN 014 - 43,30, 7 TEST 7 035 - 42,21, 0 LBL 0 015 - 34 x<>y 036 - 45,10, 0 RCL ÷ 0 016 - 43 33 R-^ 037 - 43 44 INT 017 - 43,30, 7 TEST 7 038 - 43 36 LASTx 018 - 34 x<>y 039 - 42 44 FRAC 019 - 33 R-v 040 - 45,20, 0 RCL × 0 020 - 43,30, 7 TEST 7 041 - 34 x<>y 021 - 34 x<>y 042 - 43 32 RTN ``` Quote: What is the behavior if you iterate this? Make a speculation. Most numbers will end up with 6174. Only numbers composed of the same digit will end up with 0. Quote: Try to proof your assumption. My observation was the same as described in Mysterious number 6174. (cf. "Which way to 6174?") So I guess I don't have to repeat that proof here. However I didn't ignore possible duplicates of the 55 numbers that remain after the first iteration. Quote: Can your calculator be of any help? Here's a small program that produces the 55 numbers left after the first iteration: Initialization: ```9 STO 1 EEX 3 / STO 2 ``` ```043 - 42,21,12 LBL B 055 - 42, 6, 2 ISG 2 044 - 45 1 RCL 1 056 - 43 32 RTN 045 - 9 9 057 - 42, 5, 1 DSE 1 046 - 9 9 058 - 43 20 x=0 047 - 9 9 059 - 43 32 RTN 048 - 20 × 060 - 45 1 RCL 1 049 - 45 2 RCL 2 061 - 26 EEX 050 - 43 44 INT 062 - 3 3 051 - 9 9 063 - 10 ÷ 052 - 0 0 064 - 44 2 STO 2 053 - 20 × 065 - 33 R-v 054 - 40 + 066 - 43 32 RTN ``` Now you can switch between the two programs A and B: ```B: 8991 A: 8082 A: 8532 A: 6174 B: 9081 A: 9621 A: 8352 A: 6174 (...) B: 0 A: 0 ``` The data was then used to create this graph. There's a direct proof in the same article as well. (cf. "Only 6174?") Again the HP-15C can be used to solve the system of linear equations: ```| 1 0 1 -1 | | a | | 10 | | | | | | | | 1 1 -1 0 | | b | | 9 | | | | | = | | | 0 1 -1 -1 | | c | | 1 | | | | | | | | 1 -1 0 -1 | | d | | 0 | ``` The solution is: [ a b c d ] = [ 7 6 4 1 ] I must admit that I wasn't aware of Kaprekar's constant. I just saw this arithmetic problem in that book which made me wonder why. So thanks a lot to Paul Dale for pointing this out. I know it wasn't a hard problem but still an occasion to use your best loved machines. Nevertheless I hope you enjoyed the contest. Cheers and thanks for your contributions Thomas Quote: PS: And where will all this lead us? Edited: 27 Sept 2010, 3:43 p.m.

 Re: Mini-Challenge: Zip CodeMessage #19 Posted by Thomas Klemm on 27 Sept 2010, 3:18 p.m.,in response to message #1 by Thomas Klemm Another solution for the HP-48: ```\<< SORT DUP REVLIST SWAP - IF DUP 2 GET THEN { 0 -1 9 10 } ELSE { -1 9 9 10 } END ADD \>> ``` Start with a list of 4 digits, e.g. { 4 1 5 3 }. Thomas

Go back to the main exhibit hall