How to resolve the algorithm Zeckendorf number representation step by step in the Standard ML programming language

Published on 12 May 2024 09:40 PM
#Standard ml

How to resolve the algorithm Zeckendorf number representation step by step in the Standard ML programming language

Table of Contents

Problem Statement

Just as numbers can be represented in a positional notation as sums of multiples of the powers of ten (decimal) or two (binary); all the positive integers can be represented as the sum of one or zero times the distinct members of the Fibonacci series. Recall that the first six distinct Fibonacci numbers are: 1, 2, 3, 5, 8, 13. The decimal number eleven can be written as 013 + 18 + 05 + 13 + 02 + 01 or 010100 in positional notation where the columns represent multiplication by a particular member of the sequence. Leading zeroes are dropped so that 11 decimal becomes 10100. 10100 is not the only way to make 11 from the Fibonacci numbers however; 013 + 18 + 05 + 03 + 12 + 11 or 010011 would also represent decimal 11. For a true Zeckendorf number there is the added restriction that no two consecutive Fibonacci numbers can be used which leads to the former unique solution.

Generate and show here a table of the Zeckendorf number representations of the decimal numbers zero to twenty, in order.
The intention in this task to find the Zeckendorf form of an arbitrary integer. The Zeckendorf form can be iterated by some bit twiddling rather than calculating each value separately but leave that to another separate task.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Zeckendorf number representation step by step in the Standard ML programming language

Source code in the standard programming language

val zeckList = fn from => fn to =>

 let
  open IntInf

 val rec npow = fn n => fn 0 => fromInt 1 | m => n* (npow n (m-1)) ;

 val fib = fn 0 => 1 | 1 => 1 | n => let   val rec fb = fn x => fn y => fn 1=>y | n=> fb y (x+y) (n-1)  in
        fb 0 1  n
     end;

 val argminfi =  fn n =>                                          (* lowest k with fibonacci number over n *)
   let
      val rec afb = fn k => if fib k > n then k else afb (k+1)
   in
      afb 0
   end;

 val Zeck = fn n =>
   let
      val rec calzk = fn (0,z) => (0,z)
                       | (n,z) => let  val k =  argminfi n  in
                                     calzk ( n - fib (k-1) , z + (npow 10 (k-3) ) )
				  end
   in
      #2 (calzk (n,0))
  end

 in
     List.tabulate (toInt ( to - from) ,
                    fn i:Int.int => ( from + (fromInt i),
	            Zeck ( from + (fromInt i) ))) 
end;

List.app ( fn e => print ( (IntInf.toString (#1 e)) ^"  :  "^ (IntInf.toString (#2 e)) ^ "\n" )) (zeckList 1 21) ;
1  :  1
2  :  10
3  :  100
4  :  101
5  :  1000
6  :  1001
7  :  1010
8  :  10000
9  :  10001
10  :  10010
11  :  10100
12  :  10101
13  :  100000
14  :  100001
15  :  100010
16  :  100100
17  :  100101
18  :  101000
19  :  101001
20  :  101010

zeckList 0x21e320a3 0x21e320a4 ;
val it = [(568533155, 100100100101001001001000000100100010100101)]:
 : (IntInf.int * IntInf.int) list

You may also check:How to resolve the algorithm Walk a directory/Non-recursively step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm Count in factors step by step in the Python programming language
You may also check:How to resolve the algorithm Bitwise IO step by step in the MIPS Assembly programming language
You may also check:How to resolve the algorithm Quaternion type step by step in the Factor programming language
You may also check:How to resolve the algorithm Loops/With multiple ranges step by step in the ARM Assembly programming language