/* 

  Sum of consecutive numbers in Picat.

  From Chris Smith (@aap03102) Math Newsletter #4822:
  """
    2 + 3 + 4 + 5 + 6 + 7 = 27
    1 + 2 + 3 + 4 + 5 = 15

  Find me other numbers that are the sum of consecutive numbers and
  also the concatenation of the start and end of that string of numbers!
  """

  Here are some solutions in base 10, for a and b in 1..9999:

  [base = 10,a = 1,b = 5,sum = 15,radix = [1,5,15]]
  [base = 10,a = 2,b = 7,sum = 27,radix = [2,7,27]]
  [base = 10,a = 4,b = 29,sum = 429,radix = [4,29,429]]
  [base = 10,a = 7,b = 119,sum = 7119,radix = [7,119,7119]]
  [base = 10,a = 13,b = 53,sum = 1353,radix = [13,53,1353]]
  [base = 10,a = 18,b = 63,sum = 1863,radix = [18,63,1863]]
  [base = 10,a = 33,b = 88,sum = 3388,radix = [33,88,3388]]
  [base = 10,a = 35,b = 91,sum = 3591,radix = [35,91,3591]]
  [base = 10,a = 78,b = 403,sum = 78403,radix = [78,403,78403]]
  [base = 10,a = 133,b = 533,sum = 133533,radix = [133,533,133533]]
  [base = 10,a = 178,b = 623,sum = 178623,radix = [178,623,178623]]
  [base = 10,a = 273,b = 2353,sum = 2732353,radix = [273,2353,2732353]]
  [base = 10,a = 228,b = 2148,sum = 2282148,radix = [228,2148,2282148]]
  [base = 10,a = 388,b = 2813,sum = 3882813,radix = [388,2813,3882813]]
  [base = 10,a = 710,b = 3835,sum = 7103835,radix = [710,3835,7103835]]
  [base = 10,a = 1333,b = 5333,sum = 13335333,radix = [1333,5333,13335333]]
  [base = 10,a = 1778,b = 6223,sum = 17786223,radix = [1778,6223,17786223]]
  [base = 10,a = 1701,b = 6076,sum = 17016076,radix = [1701,6076,17016076]]
  [base = 10,a = 2737,b = 7889,sum = 27377889,radix = [2737,7889,27377889]]
  [base = 10,a = 3273,b = 8728,sum = 32738728,radix = [3273,8728,32738728]]
  [base = 10,a = 3563,b = 9163,sum = 35639163,radix = [3563,9163,35639163]]

  CPU time 10.378 seconds. Backtracks: 17470097


  See below for some solution in other bases.
  There seems to be no solutions for base 2, 4, 8, 16, or 32. Why?

  There are 4 approaches:
  * go/0: CP approach (the fastest approach)
  * go2/0: Another CP approach with explicit array of all the numbers (slower)
  * go3/0: Non-CP approach, using member/2
  * go4/0: Imperative approach using foreach/1.
   

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.
% import sat.

main => go.


/* 
  Here are some solutions for N 1..4 and for all bases 2..16.
  But there are no solutions for base 2, 4, 8, 16, 32 (and 64?). Why?

  n = 4
  base = 2
  base = 3
  [base = 3,a = 2,b = 11,sum = 65,radix = [2,102,2102]]
  [base = 3,a = 7,b = 21,sum = 210,radix = [21,210,21210]]
  [base = 3,a = 11,b = 44,sum = 935,radix = [102,1122,1021122]]
  [base = 3,a = 14,b = 50,sum = 1184,radix = [112,1212,1121212]]
  base = 4
  base = 5
  [base = 5,a = 3,b = 13,sum = 88,radix = [3,23,323]]
  [base = 5,a = 3,b = 28,sum = 403,radix = [3,103,3103]]
  [base = 5,a = 63,b = 288,sum = 39663,radix = [223,2123,2232123]]
  [base = 5,a = 83,b = 333,sum = 52208,radix = [313,2313,3132313]]
  [base = 5,a = 138,b = 438,sum = 86688,radix = [1023,3223,10233223]]
  base = 6
  [base = 6,a = 1,b = 4,sum = 10,radix = [1,4,14]]
  [base = 6,a = 1,b = 9,sum = 45,radix = [1,13,113]]
  [base = 6,a = 5,b = 20,sum = 200,radix = [5,32,532]]
  [base = 6,a = 6,b = 22,sum = 238,radix = [10,34,1034]]
  [base = 6,a = 14,b = 35,sum = 539,radix = [22,55,2255]]
  [base = 6,a = 29,b = 116,sum = 6380,radix = [45,312,45312]]
  [base = 6,a = 24,b = 105,sum = 5289,radix = [40,253,40253]]
  [base = 6,a = 38,b = 134,sum = 8342,radix = [102,342,102342]]
  [base = 6,a = 41,b = 329,sum = 53465,radix = [105,1305,1051305]]
  [base = 6,a = 44,b = 341,sum = 57365,radix = [112,1325,1121325]]
  [base = 6,a = 65,b = 416,sum = 84656,radix = [145,1532,1451532]]
  [base = 6,a = 173,b = 692,sum = 224900,radix = [445,3112,4453112]]
  [base = 6,a = 468,b = 1197,sum = 607725,radix = [2100,5313,21005313]]
  [base = 6,a = 494,b = 1235,sum = 641459,radix = [2142,5415,21425415]]
  [base = 6,a = 483,b = 1219,sum = 627187,radix = [2123,5351,21235351]]
  [base = 6,a = 230,b = 806,sum = 298886,radix = [1022,3422,10223422]]
  [base = 6,a = 418,b = 1122,sum = 542850,radix = [1534,5110,15345110]]
  base = 7
  [base = 7,a = 2,b = 6,sum = 20,radix = [2,6,26]]
  [base = 7,a = 4,b = 53,sum = 1425,radix = [4,104,4104]]
  [base = 7,a = 18,b = 46,sum = 928,radix = [24,64,2464]]
  [base = 7,a = 11,b = 88,sum = 3861,radix = [14,154,14154]]
  [base = 7,a = 86,b = 258,sum = 29756,radix = [152,516,152516]]
  [base = 7,a = 130,b = 326,sum = 44916,radix = [244,644,244644]]
  [base = 7,a = 221,b = 1054,sum = 531675,radix = [434,3034,4343034]]
  [base = 7,a = 137,b = 823,sum = 329760,radix = [254,2254,2542254]]
  [base = 7,a = 732,b = 2013,sum = 1759545,radix = [2064,5604,20645604]]
  [base = 7,a = 564,b = 1740,sum = 1355904,radix = [1434,5034,14345034]]
  [base = 7,a = 914,b = 2286,sum = 2196800,radix = [2444,6444,24446444]]
  base = 8
  base = 9
  [base = 9,a = 5,b = 86,sum = 3731,radix = [5,105,5105]]
  [base = 9,a = 14,b = 50,sum = 1184,radix = [15,55,1555]]
  [base = 9,a = 11,b = 44,sum = 935,radix = [12,48,1248]]
  [base = 9,a = 50,b = 275,sum = 36725,radix = [55,335,55335]]
  [base = 9,a = 23,b = 185,sum = 16952,radix = [25,225,25225]]
  [base = 9,a = 203,b = 581,sum = 148568,radix = [245,715,245715]]
  [base = 9,a = 278,b = 695,sum = 203357,radix = [338,852,338852]]
  [base = 9,a = 95,b = 1121,sum = 624416,radix = [115,1475,1151475]]
  [base = 9,a = 581,b = 2822,sum = 3814763,radix = [715,3775,7153775]]
  [base = 9,a = 875,b = 3500,sum = 5744375,radix = [1172,4718,11724718]]
  [base = 9,a = 1580,b = 4820,sum = 10371200,radix = [2145,6545,21456545]]
  [base = 9,a = 1166,b = 4082,sum = 7654208,radix = [1535,5535,15355535]]
  base = 10
  [base = 10,a = 1,b = 5,sum = 15,radix = [1,5,15]]
  [base = 10,a = 2,b = 7,sum = 27,radix = [2,7,27]]
  [base = 10,a = 4,b = 29,sum = 429,radix = [4,29,429]]
  [base = 10,a = 7,b = 119,sum = 7119,radix = [7,119,7119]]
  [base = 10,a = 35,b = 91,sum = 3591,radix = [35,91,3591]]
  [base = 10,a = 18,b = 63,sum = 1863,radix = [18,63,1863]]
  [base = 10,a = 33,b = 88,sum = 3388,radix = [33,88,3388]]
  [base = 10,a = 13,b = 53,sum = 1353,radix = [13,53,1353]]
  [base = 10,a = 78,b = 403,sum = 78403,radix = [78,403,78403]]
  [base = 10,a = 133,b = 533,sum = 133533,radix = [133,533,133533]]
  [base = 10,a = 178,b = 623,sum = 178623,radix = [178,623,178623]]
  [base = 10,a = 710,b = 3835,sum = 7103835,radix = [710,3835,7103835]]
  [base = 10,a = 388,b = 2813,sum = 3882813,radix = [388,2813,3882813]]
  [base = 10,a = 273,b = 2353,sum = 2732353,radix = [273,2353,2732353]]
  [base = 10,a = 228,b = 2148,sum = 2282148,radix = [228,2148,2282148]]
  [base = 10,a = 3273,b = 8728,sum = 32738728,radix = [3273,8728,32738728]]
  [base = 10,a = 1701,b = 6076,sum = 17016076,radix = [1701,6076,17016076]]
  [base = 10,a = 1778,b = 6223,sum = 17786223,radix = [1778,6223,17786223]]
  [base = 10,a = 2737,b = 7889,sum = 27377889,radix = [2737,7889,27377889]]
  [base = 10,a = 3563,b = 9163,sum = 35639163,radix = [3563,9163,35639163]]
  [base = 10,a = 1333,b = 5333,sum = 13335333,radix = [1333,5333,13335333]]
  base = 11
  [base = 11,a = 3,b = 9,sum = 42,radix = [3,9,39]]
  [base = 11,a = 6,b = 39,sum = 765,radix = [6,36,636]]
  [base = 11,a = 6,b = 127,sum = 8113,radix = [6,106,6106]]
  [base = 11,a = 39,b = 105,sum = 4824,radix = [36,96,3696]]
  [base = 11,a = 39,b = 325,sum = 52234,radix = [36,276,36276]]
  [base = 11,a = 333,b = 999,sum = 444222,radix = [283,829,283829]]
  [base = 11,a = 138,b = 622,sum = 184300,radix = [116,516,116516]]
  [base = 11,a = 204,b = 765,sum = 272289,radix = [176,636,176636]]
  [base = 11,a = 435,b = 1161,sum = 580146,radix = [366,966,366966]]
  [base = 11,a = 1040,b = 5616,sum = 15232256,radix = [866,4246,8664246]]
  [base = 11,a = 1271,b = 6232,sum = 18614943,radix = [A56,4756,A564756]]
  [base = 11,a = 710,b = 4615,sum = 10399725,radix = [596,3516,5963516]]
  [base = 11,a = 3570,b = 10830,sum = 52279200,radix = [2756,8156,27568156]]
  [base = 11,a = 4791,b = 12777,sum = 70157808,radix = [3666,9666,36669666]]
  base = 12
  [base = 12,a = 3,b = 30,sum = 462,radix = [3,26,326]]
  [base = 12,a = 10,b = 55,sum = 1495,radix = [A,47,A47]]
  [base = 12,a = 35,b = 350,sum = 60830,radix = [2B,252,2B252]]
  [base = 12,a = 1573,b = 8229,sum = 32625957,radix = [AB1,4919,AB14919]]
  [base = 12,a = 504,b = 4600,sum = 10455544,radix = [360,27B4,36027B4]]
  [base = 12,a = 1418,b = 7799,sum = 29411447,radix = [9A2,461B,9A2461B]]
  [base = 12,a = 419,b = 4190,sum = 8692574,radix = [2AB,2512,2AB2512]]
  [base = 12,a = 2765,b = 11060,sum = 57346100,radix = [1725,6498,17256498]]
  [base = 12,a = 3441,b = 12432,sum = 71365008,radix = [1BA9,7240,1BA97240]]
  [base = 12,a = 8531,b = 20654,sum = 176919470,radix = [4B2B,BB52,4B2BBB52]]
  [base = 12,a = 3616,b = 12769,sum = 74994145,radix = [2114,7481,21147481]]
  [base = 12,a = 5789,b = 16541,sum = 120057245,radix = [3425,96A5,342596A5]]
  [base = 12,a = 5474,b = 16031,sum = 113524895,radix = [3202,933B,3202933B]]
  [base = 12,a = 3686,b = 12902,sum = 76445798,radix = [2172,7572,21727572]]
  base = 13
  [base = 13,a = 7,b = 176,sum = 15555,radix = [7,107,7107]]
  [base = 13,a = 20,b = 85,sum = 3465,radix = [17,67,1767]]
  [base = 13,a = 33,b = 111,sum = 5688,radix = [27,87,2787]]
  [base = 13,a = 150,b = 826,sum = 330376,radix = [B7,4B7,B74B7]]
  [base = 13,a = 293,b = 4102,sum = 8372475,radix = [197,1B37,1971B37]]
  [base = 13,a = 618,b = 5974,sum = 17656672,radix = [387,2947,3872947]]
  [base = 13,a = 1775,b = 10225,sum = 50706000,radix = [A67,4867,A674867]]
  [base = 13,a = 1034,b = 7755,sum = 29539829,radix = [617,36B7,61736B7]]
  [base = 13,a = 3348,b = 14229,sum = 95636457,radix = [16A7,6627,16A76627]]
  [base = 13,a = 8366,b = 23407,sum = 238964733,radix = [3A67,A867,3A67A867]]
  [base = 13,a = 7014,b = 21210,sum = 200348064,radix = [3267,9867,32679867]]
  [base = 13,a = 3296,b = 14112,sum = 94151168,radix = [1667,6567,16676567]]
  [base = 13,a = 5649,b = 18831,sum = 161359920,radix = [2757,8757,27578757]]
  [base = 13,a = 2451,b = 12084,sum = 70015095,radix = [1167,5667,11675667]]
  base = 14
  [base = 14,a = 3,b = 10,sum = 52,radix = [3,A,3A]]
  [base = 14,a = 5,b = 45,sum = 1025,radix = [5,33,533]]
  [base = 14,a = 8,b = 57,sum = 1625,radix = [8,41,841]]
  [base = 14,a = 11,b = 67,sum = 2223,radix = [B,4B,B4B]]
  [base = 14,a = 74,b = 186,sum = 14690,radix = [54,D4,54D4]]
  [base = 14,a = 60,b = 165,sum = 11925,radix = [44,BB,44BB]]
  [base = 14,a = 39,b = 130,sum = 7774,radix = [2B,94,2B94]]
  [base = 14,a = 543,b = 1810,sum = 1491802,radix = [2AB,934,2AB934]]
  [base = 14,a = 330,b = 1386,sum = 906906,radix = [198,710,198710]]
  [base = 14,a = 1544,b = 11001,sum = 59325305,radix = [7C4,401B,7C4401B]]
  [base = 14,a = 2195,b = 13171,sum = 84336291,radix = [B2B,4B2B,B2B4B2B]]
  [base = 14,a = 1005,b = 8845,sum = 38616925,radix = [51B,331B,51B331B]]
  [base = 14,a = 831,b = 8034,sum = 31931730,radix = [435,2CDC,4352CDC]]
  [base = 14,a = 6290,b = 22866,sum = 241659506,radix = [2414,8494,24148494]]
  [base = 14,a = 11708,b = 32197,sum = 449806725,radix = [43A4,BA3B,43A4BA3B]]
  [base = 14,a = 7599,b = 25330,sum = 291948514,radix = [2AAB,9334,2AAB9334]]
  [base = 14,a = 6059,b = 22411,sum = 232784955,radix = [22CB,824B,22CB824B]]
  [base = 14,a = 14634,b = 36586,sum = 562216330,radix = [5494,D494,5494D494]]
  [base = 14,a = 5828,b = 21949,sum = 223910397,radix = [21A4,7DDB,21A47DDB]]
  base = 15
  [base = 15,a = 1,b = 6,sum = 21,radix = [1,6,16]]
  [base = 15,a = 4,b = 12,sum = 72,radix = [4,C,4C]]
  [base = 15,a = 13,b = 78,sum = 3003,radix = [D,53,D53]]
  [base = 15,a = 7,b = 57,sum = 1632,radix = [7,3C,73C]]
  [base = 15,a = 8,b = 233,sum = 27233,radix = [8,108,8108]]
  [base = 15,a = 86,b = 215,sum = 19565,radix = [5B,E5,5BE5]]
  [base = 15,a = 68,b = 188,sum = 15488,radix = [48,C8,48C8]]
  [base = 15,a = 107,b = 857,sum = 361982,radix = [72,3C2,723C2]]
  [base = 15,a = 193,b = 1158,sum = 652533,radix = [CD,523,CD523]]
  [base = 15,a = 1286,b = 3215,sum = 4343465,radix = [5AB,E45,5ABE45]]
  [base = 15,a = 335,b = 1541,sum = 1132166,radix = [175,6CB,1756CB]]
  [base = 15,a = 583,b = 2068,sum = 1969693,radix = [28D,92D,28D92D]]
  [base = 15,a = 281,b = 1406,sum = 949781,radix = [13B,63B,13B63B]]
  [base = 15,a = 844,b = 2532,sum = 2851032,radix = [3B4,B3C,3B4B3C]]
  [base = 15,a = 754,b = 2379,sum = 2547129,radix = [354,A89,354A89]]
  [base = 15,a = 1028,b = 2828,sum = 3472328,radix = [488,C88,488C88]]
  [base = 15,a = 2832,b = 17169,sum = 143387169,radix = [C8C,5149,C8C5149]]
  [base = 15,a = 1411,b = 12036,sum = 71443911,radix = [641,3876,6413876]]
  [base = 15,a = 3173,b = 18203,sum = 160651328,radix = [E18,55D8,E1855D8]]
  [base = 15,a = 638,b = 8063,sum = 32306813,radix = [2C8,25C8,2C825C8]]
  [base = 15,a = 258,b = 5118,sum = 13066368,radix = [123,17B3,12317B3]]
  [base = 15,a = 1607,b = 12857,sum = 81367232,radix = [722,3C22,7223C22]]
  [base = 15,a = 2893,b = 17358,sum = 146475483,radix = [CCD,5223,CCD5223]]
  [base = 15,a = 803,b = 9053,sum = 40660928,radix = [388,2A38,3882A38]]
  [base = 15,a = 15428,b = 42428,sum = 781084928,radix = [4888,C888,4888C888]]
  [base = 15,a = 4313,b = 21338,sum = 218366963,radix = [1428,64C8,142864C8]]
  [base = 15,a = 20054,b = 49322,sum = 1015283072,radix = [5E1E,E932,5E1EE932]]
  [base = 15,a = 11773,b = 36478,sum = 596044603,radix = [374D,AC1D,374DAC1D]]
  [base = 15,a = 19286,b = 48215,sum = 976401965,radix = [5AAB,E445,5AABE445]]
  [base = 15,a = 12488,b = 37688,sum = 632242688,radix = [3A78,B278,3A78B278]]
  [base = 15,a = 14768,b = 41393,sum = 747671393,radix = [4598,C3E8,4598C3E8]]
  base = 16

  CPU time 1077.84 seconds. Backtracks: 0

*/
go =>
  nolog,
  N = 4,
  println(n=N),
  member(Base,2..16),
  % Base = 10,
  println(base=Base),  
  member(ALen,1..N),
  member(BLen,1..N),

  % A: start number, B: end number
  A :: 1..Base**N,
  B :: 1..Base**N,

  A #<= B,

  % AA: list representation of A, BA: list representation of B
  AA = new_list(ALen),
  AA :: 0..Base-1,
  BA = new_list(BLen),
  BA :: 0..Base-1,

  % No leading zeros
  AA[1] #> 0,
  BA[1] #> 0,

  Sum :: 1..Base**(2*N),
  Sum*2 #= (B-A+1)*(A+B),

  to_num(AA,Base,A),
  to_num(BA,Base,B),
  to_num(AA++BA,Base,Sum),

  %% all_different(AA++BA), % Just testing

  Vars = AA ++ BA ++ [A,B,Sum],
  solve($[ffc],Vars),

  if Base > 36 then
    % to_radix_string/2 only works for radix 2..26
    println([base=Base,a=A,b=B,sum=Sum])
  else 
    ARadix = to_radix_string(A,Base),
    BRadix = to_radix_string(B,Base),
    SumRadix = to_radix_string(Sum,Base),
    println([base=Base,a=A,b=B,sum=Sum,radix=[ARadix,BRadix,SumRadix]])
  end,
  fail,
  nl.


%
% Alternative approach using an explict array (X), quite slower.
%
go2 =>
  nolog,
  member(N,2..1200),
  member(StartN,1..10),
  member(EndN,1..10),
  
  X = new_list(N),
  X :: 0..10000,

  Start = new_list(StartN),
  Start :: 0..9,
  Start[1] #> 0,

  End = new_list(EndN),
  End :: 0..9,
  End[1] #> 0,

  foreach(I in 2..N)
    X[I] #= X[I-1]+1
  end,

  Sum #= sum(X),

  to_num(Start,X[1]),
  to_num(End,X[N]),
  StartEnd = Start ++ End,
  to_num(StartEnd,Sum),

  Vars = X ++ Start ++ End,
  solve($[ff,split],Vars),
  
  println([start=X[1],end=X[N],sum=Sum]),
  fail,

  nl.

/*
  Without CP.

  Quite neat, but significantly slower than the CP approach (52s vs 10s)

  [1,5,15]
  [2,7,27]
  [4,29,429]
  [7,119,7119]
  [13,53,1353]
  [18,63,1863]
  [33,88,3388]
  [35,91,3591]
  [78,403,78403]
  [133,533,133533]
  [178,623,178623]
  [228,2148,2282148]
  [273,2353,2732353]
  [388,2813,3882813]
  [710,3835,7103835]
  [1333,5333,13335333]
  [1701,6076,17016076]
  [1778,6223,17786223]
  [2737,7889,27377889]
  [3273,8728,32738728]
  [3563,9163,35639163]

  CPU time 52.338 seconds. Backtracks: 0

*/
go3 =>
  N = 4,
  Base = 10,
  member(A,1..Base**N),
  member(B,A..Base**N),
  Sum = (B-A+1)*(A+B)//2,
  Sum.to_string == A.to_string ++ B.to_string,
  println([A,B,Sum]),
  fail,
  nl.

/*
  Imperative variant of go3/0, slightly faster.

  [1,5,15]
  [2,7,27]
  [4,29,429]
  [7,119,7119]
  [13,53,1353]
  [18,63,1863]
  [33,88,3388]
  [35,91,3591]
  [78,403,78403]
  [133,533,133533]
  [178,623,178623]
  [228,2148,2282148]
  [273,2353,2732353]
  [388,2813,3882813]
  [710,3835,7103835]
  [1333,5333,13335333]
  [1701,6076,17016076]
  [1778,6223,17786223]
  [2737,7889,27377889]
  [3273,8728,32738728]
  [3563,9163,35639163]

  CPU time 51.208 seconds. Backtracks: 0

*/
go4 =>
  N = 4,
  Base = 10,
  foreach(A in 1..Base**N,B in A..Base**N)
    Sum = (B-A+1)*(A+B)//2,
    if Sum.to_string == A.to_string ++ B.to_string then
      println([A,B,Sum])
    end
  end,
  nl.


%
% 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).