/* Kaprekar's Constant in Picat. From http://www.math.hmc.edu/funfacts/ffiles/10002.5-8.shtml """ Take any four digit number (whose digits are not all identical), and do the following: % 1. Rearrange the string of digits to form the largest and smallest 4-digit numbers possible. 2. Take these two numbers and subtract the smaller number from the larger. 3. Use the number you obtain and repeat the above process. What happens if you repeat the above process over and over? Let's see... Suppose we choose the number 3141. 4311-1134=3177. 7731-1377=6354. 6543-3456=3087. 8730-0378=8352. 8532-2358=6174. 7641-1467=6174... The process eventually hits 6174 and then stays there! But the more amazing thing is this: every four digit number whose digits are not all the same will eventually hit 6174, in at most 7 steps, and then stay there! """ Also see: - http://plus.maths.org/issue38/features/nishiyama/index.html - http://en.wikipedia.org/wiki/6174_%28number%29 In this model we just try to find the constants, i.e. the fixpoints. Compare with these which calculates the full Kaprekar sequences (if they exists): - htpp://hakank.org/picat/kaprekars_constant.pi - htpp://hakank.org/picat/kaprekars_constant2.pi Fixpoints for N=2..16 --------------------- Here are the fix points for N = 2..16 (i.e. length of the numbers). Note: This does not mean that all numbers are tending to this fixpoint, just that the number is its own Kaprekar numbers. For N = 3 and N = 4 most numbers are, however, reaching the fixpoints. See note about N=3 and N=4 below. n = 2 n = 3 495 n = 4 6174 n = 5 n = 6 631764 549945 n = 7 n = 8 97508421 63317664 n = 9 864197532 554999445 n = 10 9975084201 9753086421 6333176664 n = 11 86431976532 n = 12 999750842001 997530864201 975330866421 633331766664 555499994445 n = 13 8643319766532 n = 14 99997508420001 99975308642001 99753308664201 97755108844221 97533308666421 63333317666664 n = 15 864333197666532 555549999944445 n = 16 9999975084200001 9999753086420001 9997533086642001 9977551088442201 9975333086664201 9775531088644221 9753333086666421 6333333176666664 Invariants -- - - - - One can note the similarity of some of these fixpoints: * N: 4 6174 N: 6 631764 N: 8 63317664 N: 10 6333176664 N: 12 633331766664 N: 14 63333317666664 N: 16 6333333176666664 * (N: 3 495 ) N: 9 864197532 N: 11 86431976532 N: 13 8643319766532 N: 15 864333197666532 * N: 8 97508421 N: 10 9975084201 N: 12 999750842001 997530864201 975330866421 N: 14 99997508420001 99975308642001 99753308664201 N: 16 9999975084200001 9999753086420001 9997533086642001 9975333086664201 9753333086666421 and 9775531088644221 9977551088442201 * N: 3 495 N: 6 549945 N: 9 554999445 N: 12 555499994445 N: 15 555549999944445 Exceptions for N=3 and N=4 - - - - - - - - - - - - - For N=4 the following 38 numbers reach the fixpoint of 0, not 6174: 1000 1011 1101 1110 1112 1121 1211 1222 2111 2122 2212 2221 2223 2232 2322 2333 3222 3233 3323 3332 3334 3343 3433 3444 4333 4344 4434 4443 4445 4454 4544 4555 5444 5455 5545 5554 5556 5565 5655 5666 6555 6566 6656 6665 6667 6676 6766 6777 7666 7677 7767 7776 7778 7787 7877 7888 8777 8788 8878 8887 8889 8898 8988 8999 9888 9899 9989 9998 They all that the distribution of 3 digits that are the same and then another digit. For N=3 the following 51 numbers reach 0 instead of 495: 100 101 110 112 121 122 211 212 221 223 232 233 322 323 332 334 343 344 433 434 443 445 454 455 544 545 554 556 565 566 655 656 665 667 676 677 766 767 776 778 787 788 877 878 887 889 898 899 988 989 998 For larger N with some fixpoint it's quite rare that a number reach the Kaprekar fixpoint. See http://hakank.org/picat/kaprekars_constant.pi for more on this. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. go ?=> Base = 10, % N = 9, member(N,2..16), nl, println(n=N), Map = get_global_map(), Num :: Base**(N-1)..Base**N-1, do_kaprekar(Num,N,Base, X), if not Map.has_key(X) then println(X[1]) end, Map.put(X,Map.get(X,0)+1), flush(stdout), fail, nl. go => true. % % ensure that X don't contains all the same digits % not_same_digits(N,X) => sum($[ ((X div (10**I)) mod 10) #!= ((X div (10**J)) mod 10) : I in 0..N-1, J in I+1..N-1]) #>= 1. do_kaprekar(Num,N,Base, X) => Rows = 2, % We just want the fixed points MaxVal = Base**N-1, % decision variables X = new_list(Rows), X :: 0..MaxVal, X[1] #>= 10**(N-1), % N-digit number X[1] #= Num, X[2] #> 0, X[2] #= X[1], % Get the fixpoints Vs = [], foreach(I in 2..Rows) kaprekar(X[I-1], X[I], N, Base, V), % add the underlying variables Vs := Vs ++ [V] end, Vars = Vs ++ X, solve($[split],Vars). % % The Kaprakar procedure % % We return all the decision variables kaprekar(S, T, N, Base, Vars) => MaxVal = Base**N-1, SNum = new_list(N), SNum :: 0..Base-1, SOrdered = new_list(N), SOrdered :: 0..Base-1, SReverse = new_list(N), SReverse :: 0..Base-1, OrdNum :: 0..MaxVal, RevNum :: 0..MaxVal, to_num(SNum, Base, S), sort_increasing(SNum, SOrdered,P), % sort_decreasing(SNum, SReverse), reverse_c(SOrdered, SReverse), to_num(SOrdered, Base, OrdNum), to_num(SReverse, Base, RevNum), T #= RevNum - OrdNum, Vars = SOrdered ++ SReverse ++ P ++ [SNum,OrdNum,RevNum]. % % reverse an array % reverse_c(X, Rev) => Len = X.len, foreach(I in 1..Len) Rev[I] #= X[Len-I+1] end. % % converts a number Num to/from a list of integer List given a base Base % to_num(List, Base, Num) => Len = length(List), Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]). to_num(List, Num) => to_num(List, 10, Num). % % Y is a sorted version of X % sort_increasing_xxx(X,Y,P) => N = X.len, P = new_list(N), P :: 1..N, all_different(P), foreach(I in 1..N) % y[p[i]] == x[i] element(P[I],Y,X[I]) end, increasing(Y). sort_increasing(X,Y,P) => P = new_list(X.len), P :: 1..X.len, all_different(P), permutation3(X,P,Y), increasing(Y). % The permutation from A <-> B using the permutation P permutation3(A,P,B) => foreach(I in 1..A.length) % PI #= P[I], % BI #= B[I], % element(PI, A, BI) element(P[I], A, B[I]) end.