Mini-Challenge: Zip Code



#20

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

  1. Start with 4153
  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?


#21

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


#22

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

#23

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.

#24

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

#25

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.


#26

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

  • 4444 Rümlingen
  • 8888 Heiligkreuz

Best regards

Thomas

#27

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


#28

Quote:
Kaprekar's constant

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

Patrice

#29

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

#30

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.

#31

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.

#32

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

#33

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

#34

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


#35

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.


#36

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
#37

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.

#38

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


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP PRIME: APP program code DISAPPEARS !! Joseph Ec 0 161 11-25-2013, 11:35 AM
Last Post: Joseph Ec
  Where to the 32-bit version of User Code Utiltiy for HP-41 ? Olivier (Wa) 2 194 09-26-2013, 01:55 AM
Last Post: Olivier (Wa)
  A HP42S Code Editor Andreas 9 528 09-22-2013, 03:17 AM
Last Post: Andreas
  HPCC Mini Conference 2013 hugh steers 6 350 09-13-2013, 04:27 PM
Last Post: BruceH
  Dynamic Gaussian Quadrature code in Excel VBA Namir 4 298 07-30-2013, 07:37 PM
Last Post: Namir
  Picture from the Mini-HHC (LA) Geir Isene 11 521 07-07-2013, 01:06 PM
Last Post: Jim Horn
  My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 1,536 03-07-2013, 03:44 AM
Last Post: Walter B
  HP-65 Morse Code Dan Lewis 7 390 01-29-2013, 05:22 PM
Last Post: Mike T.
  WP 34S mini-challenge (B) Gerson W. Barbosa 17 663 12-27-2012, 04:39 PM
Last Post: Marcus von Cube, Germany
  Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 649 10-05-2012, 10:36 PM
Last Post: David Hayden

Forum Jump: