/* Multiplicative sequence in Picat. From "Mind Your Decision" "Monday puzzle: can you guess the 1000th number in my list?" http://mindyourdecisions.com/blog/2013/08/12/monday-puzzle-can-you-guess-the-1000-number-in-my-list/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+mindyourdecisions+%28Mind+Your+Decisions%29 """ I have written a long, long sequence of positive whole numbers. Can you guess the 1,000 item on my list? I will give you 3 clues about my sequence of numbers {a[n]}: 1. The list of numbers is strictly increasing (a[k] + 1 > a[k]) 2. The second number in my list is 2 (a[2] = 2) 3. My list always has a(m*n) = a[m]*a[n] when the two numbers m and n are relatively prime. (Call this the multiplicative property). For example, a[60] = a[4]*a[15] because 4 and 15 are relatively prime. What possible number(s) could I have written for a1000? I admit I did not solve this puzzle on my own. Can you? ... Source of puzzle: this is puzzle 42 from the website qbyte.org [ http://www.qbyte.org/puzzles/puzzle05.html "Multiplicative sequence" ] """ Note: Here are the number of solutions for some N << 1000 (for the somewhat arbitrary domain of X in 1..2*N): N: #num solutions ------------------------------ 2: 1 (prime: 1) N*N:3 3: 4 (prime: 1) N*N:4 4: 15 (prime: 0) N*N:5 5: 56 (prime: 1) N*N:6 6: 20 (prime: 0) N*N:7 7: 70 (prime: 1) N*N:8 8: 38 (prime: 0) N*N:9 9: 140 (prime: 0) N*N:10 10: 68 (prime: 0) N*N:11 11: 276 (prime: 1) N*N:12 For 12..100: when N is a prime then there is > 1 solutions. Then the number of solutions is 1+N, i.e. the last element (X[N]) will be all the values in the range N..2*N. I don't understand the number of solutions for N < 12, though. 2: 1 (prime: 1) N*N:3 3: 4 (prime: 1) N*N:4 4: 15 (prime: 0) N*N:5 5: 56 (prime: 1) N*N:6 6: 20 (prime: 0) N*N:7 7: 70 (prime: 1) N*N:8 8: 38 (prime: 0) N*N:9 9: 140 (prime: 0) N*N:10 10: 68 (prime: 0) N*N:11 11: 276 (prime: 1) N*N:12 12: 1 (prime: 0) N*N:13 13: 14 (prime: 1) N*N:14 14: 1 (prime: 0) N*N:15 15: 1 (prime: 0) N*N:16 16: 1 (prime: 0) N*N:17 17: 18 (prime: 1) N*N:18 18: 1 (prime: 0) N*N:19 19: 20 (prime: 1) N*N:20 20: 1 (prime: 0) N*N:21 21: 1 (prime: 0) N*N:22 22: 1 (prime: 0) N*N:23 23: 24 (prime: 1) N*N:24 24: 1 (prime: 0) N*N:25 25: 26 (prime: 0) N*N:26 26: 1 (prime: 0) N*N:27 27: 1 (prime: 0) N*N:28 28: 1 (prime: 0) N*N:29 29: 30 (prime: 1) N*N:30 30: 1 (prime: 0) N*N:31 31: 32 (prime: 1) N*N:32 32: 1 (prime: 0) N*N:33 33: 1 (prime: 0) N*N:34 34: 1 (prime: 0) N*N:35 35: 1 (prime: 0) N*N:36 36: 1 (prime: 0) N*N:37 37: 38 (prime: 1) N*N:38 38: 1 (prime: 0) N*N:39 39: 1 (prime: 0) N*N:40 40: 1 (prime: 0) N*N:41 41: 42 (prime: 1) N*N:42 42: 1 (prime: 0) N*N:43 43: 44 (prime: 1) N*N:44 44: 1 (prime: 0) N*N:45 45: 1 (prime: 0) N*N:46 46: 1 (prime: 0) N*N:47 47: 48 (prime: 1) N*N:48 48: 1 (prime: 0) N*N:49 49: 50 (prime: 0) N*N:50 50: 1 (prime: 0) N*N:51 51: 1 (prime: 0) N*N:52 52: 1 (prime: 0) N*N:53 53: 54 (prime: 1) N*N:54 54: 1 (prime: 0) N*N:55 55: 1 (prime: 0) N*N:56 56: 1 (prime: 0) N*N:57 57: 1 (prime: 0) N*N:58 58: 1 (prime: 0) N*N:59 59: 60 (prime: 1) N*N:60 60: 1 (prime: 0) N*N:61 61: 62 (prime: 1) N*N:62 62: 1 (prime: 0) N*N:63 63: 1 (prime: 0) N*N:64 64: 1 (prime: 0) N*N:65 65: 1 (prime: 0) N*N:66 66: 1 (prime: 0) N*N:67 67: 68 (prime: 1) N*N:68 68: 1 (prime: 0) N*N:69 69: 1 (prime: 0) N*N:70 70: 1 (prime: 0) N*N:71 71: 72 (prime: 1) N*N:72 72: 1 (prime: 0) N*N:73 73: 74 (prime: 1) N*N:74 74: 1 (prime: 0) N*N:75 75: 1 (prime: 0) N*N:76 76: 1 (prime: 0) N*N:77 77: 1 (prime: 0) N*N:78 78: 1 (prime: 0) N*N:79 79: 80 (prime: 1) N*N:80 80: 1 (prime: 0) N*N:81 81: 1 (prime: 0) N*N:82 82: 1 (prime: 0) N*N:83 83: 84 (prime: 1) N*N:84 84: 1 (prime: 0) N*N:85 85: 1 (prime: 0) N*N:86 86: 1 (prime: 0) N*N:87 87: 1 (prime: 0) N*N:88 88: 1 (prime: 0) N*N:89 89: 90 (prime: 1) N*N:90 90: 1 (prime: 0) N*N:91 91: 1 (prime: 0) N*N:92 92: 1 (prime: 0) N*N:93 93: 1 (prime: 0) N*N:94 94: 1 (prime: 0) N*N:95 95: 1 (prime: 0) N*N:96 96: 1 (prime: 0) N*N:97 97: 98 (prime: 1) N*N:98 98: 1 (prime: 0) N*N:99 99: 1 (prime: 0) N*N:100 100: 1 (prime: 0) N*N:101 sols=[1,4,15,56,20,70,38,140,68,276,1,14,1,1,1,18,1,20,1,1,1,24,1,26,1,1,1,30,1,32,1,1,1,1,1,38,1,1,1,42,1,44,1,1,1,48,1,50,1,1,1,54,1,1,1,1,1,60,1,62,1,1,1,1,1,68,1,1,1,72,1,74,1,1,1,1,1,80,1,1,1,84,1,1,1,1,1,90,1,1,1,1,1,1,1,98,1,1,1] (OEIS don't recognize the sequence 1,4,15,56,20,70,38,140,68,276) And some larger values 991: 992 (prime: 1) 2*N:992 992: 1 (prime: 0) 2*N:993 993: 1 (prime: 0) 2*N:994 994: 1 (prime: 0) 2*N:995 995: 1 (prime: 0) 2*N:996 996: 1 (prime: 0) 2*N:997 997: 998 (prime: 1) 2*N:998 998: 1 (prime: 0) 2*N:999 999: 1 (prime: 0) 2*N:1000 1000: 1 (prime: 0) 2*N:1001 1001: 1 (prime: 0) 2*N:1002 1002: 1 (prime: 0) 2*N:1003 1003: 1 (prime: 0) 2*N:1004 1004: 1 (prime: 0) 2*N:1005 1005: 1 (prime: 0) 2*N:1006 1006: 1 (prime: 0) 2*N:1007 1007: 1 (prime: 0) 2*N:1008 1008: 1 (prime: 0) 2*N:1009 1009: 1010 (prime: 1) 2*N:1010 1010: 1 (prime: 0) 2*N:1011 1011: 1 (prime: 0) 2*N:1012 1012: 1 (prime: 0) 2*N:1013 1013: 1014 (prime: 1) 2*N:1014 This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import cp. main => go. go ?=> N = 1000, seq(N, X), writeln(x=X), nl, fail. go => true. go2 => Sols = [], foreach(N in 2..100) All = findall(X, seq(N,X)), Len = All.length, Prime = cond(prime(N), 1, 0), NN = 1+N, printf(" %2d: %d (prime: %d) 2*N:%d\n", N,Len, Prime, NN), Sols := Sols ++ [Len] end, writeln(sols=Sols), nl. go3 ?=> N = 13, seq(N, X), writeln(x=X), nl, fail. go3 => true. go4 => Sols = [], % Got some larger primes foreach(N in 991..1013) All = findall(X, seq(N,X)), Len = All.length, Prime = cond(prime(N), 1, 0), NN = 1+N, printf(" %2d: %d (prime: %d) 2*N:%d\n", N,Len, Prime, NN), Sols := Sols ++ [Len] end, writeln(sols=Sols), nl. seq(N,X) => X = new_array(N), X :: 1..N*2, % note: arbitrary domain 1..N*N foreach(I in 1..N, J in 1..N, I <= J, I*J <= N, I mod J != 0) % X[I*J] #= X[I]*X[J] X[I]*X[J] #= X[I*J] end, foreach(I in 2..N) X[I-1] #< X[I] end, X[2] #= 2, solve([ff], X).