▼
Posts: 735
Threads: 34
Joined: May 2007
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:
 Select the zip code of a Swiss location.
 Compose the maximum number of the four digits.
 Compose the smallest possible number of the four digits.
 Calculate the difference.
Example
 Start with 4153
 The maximum number made of these four digits is: 5431
 The minimal number made of these four digits is: 1345
 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 HP15C here within a couple of days.
Hope you have as much fun as I had.
Thomas
PS: And where will all this lead us?
▼
Posts: 320
Threads: 59
Joined: Dec 2006
Question: does it always require to be four digits. That is will a zip of 12 (or 0012) transition to 21000012 = 2088
If so, I'm getting just about nothing but cycles. Sadly I'm not using an HP, though.
CHUCK
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
That is will a zip of 12 (or 0012) transition to 21000012 = 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
Posts: 320
Threads: 59
Joined: Dec 2006
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.
Posts: 735
Threads: 34
Joined: May 2007
It appears that Wikipedia and
MathWorld (or rather Sloane) disagree on the values that will lead to 0.
Wikipedia:
Quote:
The only fourdigit 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 fourdigits 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 4digit 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 4digit 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
Posts: 776
Threads: 25
Joined: Jun 2007
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.
▼
Posts: 735
Threads: 34
Joined: May 2007
The only possible Swiss ZIP codes made of the same digits are:
 4444 Rümlingen
 8888 Heiligkreuz
Best regards
Thomas
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 274
Threads: 23
Joined: Sep 2007
Quote:
Kaprekar's constant
One of my favorite too, and already fun with just a paper and a pen !
Patrice
Posts: 776
Threads: 25
Joined: Jun 2007
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?)
Posts: 3,283
Threads: 104
Joined: Jul 2005
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
ZInt(Z/10)x10>A: 'get right most digit
For 1>J To N: 'find proper place for digit
If Z[J]<A:Then
A>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+1I]>B: 'same as above but in reverse digit order
Next:
AB>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 17N,1,A:
Locate 17N,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.
Posts: 57
Threads: 0
Joined: Sep 2010
Hi Thomas and hi everybody!
This is a simple HP 50g solution for your challenge.
My stack diagram is: (Level(n), Level(n1), ...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.
Posts: 83
Threads: 5
Joined: Oct 2007
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
▼
Posts: 83
Threads: 5
Joined: Oct 2007
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(da)+90(cb)
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
▼
Posts: 735
Threads: 34
Joined: May 2007
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 10^{3}:
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
▼
Posts: 83
Threads: 5
Joined: Oct 2007
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(da)+900(cb). 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.
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
I don't have RCL arithmetic at my disposal
One of the reasons why I chose HP15C.
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
Posts: 735
Threads: 34
Joined: May 2007
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 HP15C 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 Rv 028  30 
008  43,30, 7 TEST 7 029  9 9
009  34 x<>y 030  9 9
010  33 Rv 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 Rv 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 Rv
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 HP15C 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?
6174 Sörenberg
Edited: 27 Sept 2010, 3:43 p.m.
Posts: 735
Threads: 34
Joined: May 2007
Another solution for the HP48:
\<<
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
