/* 

  Fusc sequence in Picat.

  http://rosettacode.org/wiki/Fusc_sequence
  """
  Definitions

The   fusc   integer sequence is defined as:

              fusc(0) = 0
              fusc(1) = 1
              for n>1,   the   nth   term is defined as:

                      if   n   is even;     fusc(n) = fusc(n/2)
                      if   n   is   odd;     fusc(n) = fusc((n-1)/2)   +   fusc((n+1)/2)


Note that MathWorld's definition starts with unity, not zero.   This task will be using the OEIS' version   (above).


An observation

                          fusc(A) = fusc(B)

where   A   is some non-negative integer expressed in binary,   and where   B   is the binary value of   A   reversed.


Fusc numbers are also known as:

              fusc function   (named by Dijkstra, 1982)
              Stern's Diatomic series   (although it starts with unity, not zero)
              Stern-Brocot sequence   (although it starts with unity, not zero)


Task

              show the first   61   fusc numbers (starting at zero) in a horizontal format.
              show the fusc number (and its index) whose length is greater than any previous fusc number length.

                      (the length is the number of decimal digits when the fusc number is expressed in base ten.)

              show all numbers with commas   (if appropriate).
              show all output here.
  """

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

*/

% import v3_utils.
% import util.
% import cp.


main => go.


go =>
  println("First 61 fusc numbers:"),
  println([fusc(I) : I in 0..60]),
  nl,
  println("Points in the sequence whose length is greater than any previous fusc number length:\n"),
  println("   Index     fusc  Len"),  
  largest_fusc_string(20_000_000).


go2 =>
  println("First 61 fusc numbers:"),
  println([fusc(I) : I in 0..60]),
  nl,
  println("Points in the sequence whose length is greater than any previous fusc number length:\n"),
  NumDigits = 0,
  N = 0,
  LargestF = N,
  println("   Index     fusc    Len"),
  while (N <= 20_000_000)
    F = fusc(N),
    Len = F.to_string.len,
    if Len > NumDigits then
      printf("%8d %8d %4d\n",N,F,Len),
      NumDigits := Len,
      LargestF := F
    end,
    N := N + 1
  end,
  nl.
go2 => true.


table
fusc(0) = 0.
fusc(1) = 1.
fusc(N) = fusc(N//2), even(N) => true.
fusc(N) = fusc((N-1)//2) + fusc((N+1)//2) => true.


largest_fusc_string(Limit) =>
  largest_fusc_string(0,Limit,0).

largest_fusc_string(Limit,Limit,_). 
largest_fusc_string(N,Limit,LargestLen) :-
  N <= Limit,
  F = fusc(N),
  Len = F.to_string.len,
  (Len > LargestLen ->
     printf("%8d %8d %4d\n",N,F,Len),     
     LargestLen1 = Len
   ;
     LargestLen1 = LargestLen
  ),
  largest_fusc_string(N+1,Limit,LargestLen1).