▼
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 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?
▼
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 2100-0012 = 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 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
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 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
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
Z-Int(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+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.
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(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.
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(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
▼
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 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
▼
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(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.
▼
Posts: 735
Threads: 34
Joined: May 2007
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
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 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?
6174 Sörenberg
Edited: 27 Sept 2010, 3:43 p.m.
Posts: 735
Threads: 34
Joined: May 2007
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
|