Faculty for Electrical Engineering and Informatics, BME
Engineering Programme in English
MSc Course in Software Engineering
Autumn semester 2007/08

Higher-order Functional Programming

Small Homework Small-headed

Version 1
Last modification: 26-10-2007

Task description

Small-headed is a sequence of numbers if its first element is smaller then the last, the second element is smaller than the second last, and so on... To be more precise: The a1, a2, ..., an sequence is small-headed, if a1 > 0, and for all i, 1 ≤ i ≤ n div 2 (where div is integer division), ai < an+1-i. Examples: 4; 1 2; 4 2 5 3 5; 1 2 3 4 3 2. Counter-examples: 1 1; 4 2 5 3 4; 1 2 3 3 1 0.

SML-specification

Write a function called smallheaded which satisfies the following: 

(* smallheaded : int -> int
   smallheaded a = b, where 'b' >= 2 is the smallest number, for which
   the digits of 'a' written in 'b'-base form a small-headed number sequence
*)
You are allowed to define auxiliary functions.

Examples:

smallheaded 4   = 5 (* because 45 = 4 is smallheaded, but 44 = 1 0, 43 = 1 1, 42 = 1 0 0 are not *)

smallheaded 11  = 3 (* because 113 = 1 0 2 is smallheaded, but 112 = 1 0 1 1 are not *)

smallheaded 145 = 7 (* because 1457 = 2 6 5 is smallheaded, but... *)

smallheaded 293 = 3 (* because 2933 = 1 0 1 2 1 2 is smallheaded, but ... *)
In the examples, dr denote the decimal number d written in r-base.