Mini-Challenge: Zip Code « Next Oldest | Next Newest »

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?

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

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

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.

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

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.

The only possible Swiss ZIP codes made of the same digits are:

• 4444 Rümlingen
• 8888 Heiligkreuz

Best regards

Thomas

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

Quote:
Kaprekar's constant

One of my favorite too, and already fun with just a paper and a pen !

Patrice

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?)

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.

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.

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
```

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
```

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

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.

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
```

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:

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.

Another solution for the HP-48:

```\<<
SORT DUP REVLIST
SWAP -
IF DUP 2 GET
THEN { 0 -1 9 10 }
ELSE { -1 9 9 10 }