/* Book pages in Picat. A book's pages are numbered with 2989 digits. How many pages? The number of digits of a certain length: 1 = 9 (1..9 s:1..9) 2 = 90 (10..99 s:11..189) 3 = 900 (100..999 s:192..2889) 4 = 9000 (1000..9999) (In general X=asum([I*9*10**(I-1) : I in 1..10]) X = [9,189,2889,38889,488889,5888889,68888889,788888889,8888888889,98888888889] ) 1) start: 2989 2) 2889 < 2989 < 9999 so it must be a 4 digit number 3) 2989-2889=100 4) T = 100 / 4 = 25 -> X = 9 + 99 + 999 + 25 = 1024 * CP approach (go/0) Picat> book_page_numbers(2989,X,P) X = [9,90,900,25] P = 1024 * "Algorithmic" approach (first part of go4/0) [n = 2989,s = 1,t = 9,p = 0] [n = 2980,s = 2,t = 90,p = 9] [n = 2800,s = 3,t = 900,p = 99] [n = 100,s = 4,t = 9000,p = 999] add = 25 p = 1024 num_digits = 2989 num_pages = 1024 book_pages_numbers/3 is kind of reversible: - Picat> book_page_numbers(2989,X,P) X = [9,90,900,25] P = 1024 - Picat> book_page_numbers(D,X,1234567890123) D = 14938271460501 X = [9,90,900,9000,90000,900000,9000000,90000000,900000000,9000000000,90000000000,900000000000,234567890124] Aside: The sequence of accumulating the sum of units Picat> X=[I*9*10**(I-1) : I in 1..10] X = [9,180,2700,36000,450000,5400000,63000000,720000000,8100000000,90000000000] Picat X=asum([I*9*10**(I-1) : I in 1..10]) X = [9,189,2889,38889,488889,5888889,68888889,788888889,8888888889,98888888889] is the OEIS sequence https://oeis.org/A033713 : """ Number of zeros in numbers 1 to 999..9 (n digits). ... a(n) = (1/9)*((n-1)*(10^n)-n*10^(n-1)+1) """ Cf number_of_lockers.pi for a similar problem. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp,util. main => go. go ?=> Number = 2989, book_page_numbers(2989,X,P), println(number=Number), println(number_of_pages=P), println(x=X), foreach(I in 1..X.len) printf("We have %d numbers of length %d\n",X[I],I) end, printf("I.e. in total %d numbers (=pages)\n", P), fail, nl. go => true. % % Testing the variants of book_page_numbers/3 % go2 ?=> % Fix number of digits All1 = [[D,X,P] : D in 1..100,book_page_numbers(D,X,P)], println(fix_number_of_digits=All1), % Fix the number of pages All2 = [[D,X,P] : P in 1..100,book_page_numbers(D,X,P)], println(fix_number_of_pages=All2), % fix the length of X bp.length(X3,2),findall([D,X3,P],book_page_numbers(D,X3,P))=All3, println(fix_length_of_x=All3), nl. go2 => true. % % Brute force (and to get some intuition about the problem). % go3 ?=> NumDigits = 2989, Map = new_map(), S = 0, Found = false, foreach(I in 1..NumDigits,Found == false) Len = number_len(I), Map.put(Len,Map.get(Len,0)+1), S := S + Len, println([i=I,len=Len,s=S]), if S == NumDigits then Found := I end end, println(found=Found), println(map=Map), nl. go3 => true. % % Algorithmic approach % % go4 ?=> N = 2989, book_page_numbers_alg(N,NumPages,true), println(num_digits=N), println(num_pages=NumPages), nl, foreach(I in 1..16) P1 = [(J mod 10).to_string : J in 1..I].join('').to_int, book_page_numbers(D,_X,P1), book_page_numbers_alg(D,P), println([num_pages=P,num_digits=D]) end, nl, % check one of these with printing book_page_numbers_alg(18641975130864201,NumPages,true), nl. go4 => true. % % "Logic programming" approach % go5 ?=> NumDigits = 2989, book_page_numbers_alg2(NumDigits,P), println(numDigits=NumDigits), println(numPages=P), nl, NumDigits := 14938271460501, % 2989, book_page_numbers_alg2(NumDigits,P2), println(numDigits=NumDigits), println(numPages=P2), nl. go5 => true. go6 ?=> _ = random2(), % NumPagesRand = 1+ random() mod 1000000000, NumPagesRand = 310444, book_page_numbers(NumDigits,X,NumPagesRand), println([numDigits=NumDigits,x=X,numpages=NumPagesRand, mod=(NumDigits div NumPagesRand) ]), fail, nl. go6 => true. % % All solutions of length 5 % go7 ?=> N = 16, X = new_list(N), book_page_numbers(D,X,P), println([D,X,P]), fail, nl. go7 => true. % % Another way, from number_of_lockers.pi % go8 => member(N,2..10), % for some length... S=[9*10**(I-1):I in 1..N], % The bases % Fill the first N-1 slots with pages member(Slots,1..N-1), % And then add X pages of digit length N member(X,0..S[Slots+1]), SS = S[1..Slots]++[X], NumPages = sum(SS), NumDigits = sum([I*SS[I] : I in 1..Slots+1]), NumDigits == 2989, println(ss=SS), println(x=X), println(num_pages=NumPages), println(num_digits=NumDigits), nl. % % Brute force % go9 => NumDigits = 2989, % There are more digits than pages so it's a legitimate limit member(NumPages,1..NumDigits), [Page.to_string() : Page in 1..NumPages].flatten.len == NumDigits, println(num_pages=NumPages), nl. number_len(N) = ceiling(log10(N+1)). asum(S) = [ sum([S[J] : J in 1..I]) : I in 1..S.len]. % % Closed form for the sum of digits for a certain length of numbers % of length 1..N. % s(N) = ((N-1)*(10**N)-N*10**(N-1)+1) div 9. % % book_page_numbers(NumDigits,X,NumPages) % % "Reversible" (kind of): % - Calculate the number of pages given the number of digits % - Calculate the number of digits given the number of pages % - Calculate the number of digits and pages given the length of X % % The difference between this variant and an "ordinary" base system % is that we cannot use a slot S[I+1] unless the slot S[I] % is filled. % book_page_numbers(NumDigits,X,NumPages) => if nonvar(NumDigits) then N = number_len(NumDigits) elseif nonvar(NumPages) then N = number_len(NumPages) else N = X.length end, S=[9*10**(I-1) : I in 1..N], % The "bases" X = new_list(N), X :: 0..sum(S), sum([X[I]*I : I in 1..N]) #= NumDigits, sum(X) #= NumPages, % Restrict the domains for each slot (unit) foreach(I in 1..N) X[I] :: 0..S[I] end, % In order for X[I] to be > 0 we must have filled % all slots (units) in X[I-1] foreach(I in 2..N) X[I] #> 0 #=> (X[I-1] #= S[I-1]) end, solve(X). % % Algorithmic approach. % Not reversible (just calculating number of pages) % book_page_numbers_alg(N,NumPages) => book_page_numbers_alg(N,NumPages,false). book_page_numbers_alg(N,NumPages,Print) => P = 0, % number of pages S = 1, % length of the number while (N > 0) T = 9*10**(S-1), if Print then println([n=N,s=S,t=T,p=P]) end, if N <= T then if N mod S == 0 then if Print then println(add=(N div S)) end, P := P + (N div S) else % Ah, this is not a possible number of digits! P := 0 end, N := 0 % end the loop else P := P + T, N := N - T*S, S := S + 1 end end, if Print then println(p=P) end, NumPages = P. % Algorithmic approach using Horn clauses % Not reversible (just calculating number of pages given the number of digits). book_page_numbers_alg2(NumDigits,NumPages) :- book_page_numbers_alg2(NumDigits,1,0,NumPages). book_page_numbers_alg2(0,_Len,NumPages,NumPages). book_page_numbers_alg2(NumDigits,Len,NumPages1,NumPages) :- NumDigits > 0, T = 9*10**(Len-1), NumDigits <= T, NumDigits mod Len == 0, book_page_numbers_alg2(0,Len,NumPages1+(NumDigits div Len),NumPages). book_page_numbers_alg2(NumDigits,Len,NumPages1,NumPages) :- T = 9*10**(Len-1), NumDigits > T, NumDigits1 = NumDigits - T*Len, book_page_numbers_alg2(NumDigits1,Len+1,NumPages1+T,NumPages).