Finding Digit Strings In Powers Of Two
September 24, 2013
We compute all the powers of two and save them in the closure of the search function so they only have to be computed once instead of each time a search is performed. We keep track of the powers of two and double at each step instead of recomputing each time from scratch:
(define search
(let ((twos (make-vector 10000)))
(do ((i 0 (+ i 1)) (t 1 (* t 2))) ((= i 10000))
(vector-set! twos i (number->string t)))
(lambda (target)
(let loop ((i 0))
(cond ((= i 10000) #f)
((string-find (number->string target)
(vector-ref twos i)) i)
(else (loop (+ i 1))))))))
The powers of two are stored as strings, and the search in the body of the function calls string-find from the Standard Prelude to search each power of two. Here are some examples:
> (search 42)
19
> (search 1234567)
8792
This task was easy for us because Scheme provides big integers and conversions to strings natively; it will be harder in languages that don’t provide those features. You can run the program at http://programmingpraxis.codepad.org/hEsGGLRz.
Programming Praxis 
Rather easy in Python. The functions returns -1 of no index is found.
POW2 = [2 **i for i in xrange(10000)] def find_pow2(n): target = str(n) for i, p in enumerate(POW2): if target in str(p): return i return -1I rather like Haskell’s
Maybe.import Data.List (isInfixOf) powersOf2 :: [Integer] powersOf2 = map (2^) [0..] findPow2 :: String -> Maybe Int findPow2 s = aux 0 where aux i | i > 10000 = Nothing | isInfixOf s $ show (powersOf2 !! i) = Just i | otherwise = aux $ i + 1Graham: The corresponding idiom in Scheme is to return an empty list ‘() for Nothing and a non-empty list containing the value ‘(x) for Just. Those two return values are easy to distinguish by the null? and pair? predicates, and since both are lists there is no issue of type mis-match as there would be if you returned say an integer for the value x or the boolean #f for Nothing.
Paul and Graham: I think for both of you it would be quicker to build your list of powers of two by repeatedly multiplying by two, as the suggested solution does, rather than exponentiating at each step.
Indeed it is slower to use 2**i for each step. Here a version where the string representations for all powers arecalculated first (costs a little time).
POW2 = [] x = 1 for i in xrange(10000): POW2.append(str(x)) x *= 2 def find_pow2(n): target = str(n) for i, p in enumerate(POW2): if target in p: return i return -1Fair enough!
import Data.List (isInfixOf) powersOf2 :: [Integer] powersOf2 = 1 : map (2*) powersOf2 findPow2 :: String -> Maybe Int findPow2 s = aux 0 where aux i | i > 1000 = Nothing | isInfixOf s $ show (powersOf2 !! i) = Just i | otherwise = aux $ i + 1I like the Scheme idiom and the Python version of returning -1 (or even throwing an exception,
if the setting is right). I’m just recently somewhat enamored with Haskell’s types, though; they
make the meaning of the code clear to me in a way that these idioms don’t, I guess.
//Using Java
Double[] pow = new Double[1000];
private void calculatePOW()
{
for(int i=0;i<1000;i++)
pow[i] = Math.pow(2,i);
}
public int searchinPOW(int x)
{
int index = -1;
for(int i=0;i<pow.length;i++)
{
double power = pow[i];
if(String.valueOf(power).contains(String.valueOf(x)))
{
index = i;
break;
}
}
return index;
}
Forgive my formatting !!
In Racket:
#lang racket (require srfi/13) (define (in-unfold f e) (letrec ([ps (stream-cons e (stream-map f ps))]) ps)) (define (find-power s) (for/first ([n (in-unfold (curry * 2) 1)] [i (in-range 0 10000)] #:when (string-contains (number->string n) s)) i)) ;; > (find-power "42") ;; 19 ;; > (find-power "42679493") ;; #fHere is a C# solution with caching.
I used a suffix trie to store the number sequences (without the compression the your usual suffix trie has).
The numbers are stored implicitly as indexes in the children.
I also annotated the minimum base-two exponent that can reach each node in the suffix tree.
So if a digit sequence has been seen before, its O(n) performance (n = amount of digits).
public static class DigitStringPowerTwoSearch { private static SuffixTreeNode suffixRoot; private static short currentExponent; private static List<int> currentDigits; static DigitStringPowerTwoSearch () { FlushCache (); } internal static void FlushCache() { // Exposed as internal really for unit tests only currentExponent = 0; currentDigits = new List<int> { 1 }; suffixRoot = new SuffixTreeNode (); AddDigitsToTree (currentDigits, 0, 0); } public static int FindMinBaseTwoExponent(ulong target) { var targetDigits = ToDigitArray(target); while (currentExponent <= 10000) { short exponent = FindMinExponentInTree(targetDigits); if (exponent >= 0) return exponent; AddNextExponentToTree(); } throw new ArgumentOutOfRangeException ("target", "target's digits do not exist in a base two number with exponent " + "less or equal to 10,000"); } private static void AddNextExponentToTree() { DoubleDigits (currentDigits); currentExponent++; for (int i = 0; i < currentDigits.Count; i++) { AddDigitsToTree (currentDigits, i, currentExponent); } } private static void AddDigitsToTree(IList<int> digits, int startIndex, short exponent) { SuffixTreeNode current = suffixRoot; for (int i = startIndex; i < digits.Count; i++) { int digit = digits [i]; if (current.Children == null) { current.Children = new SuffixTreeNode[10]; } if (current.Children [digit] == null) { var newNode = new SuffixTreeNode { MinExponent = exponent }; current.Children [digit] = newNode; current = newNode; } else { current = current.Children [digit]; // Here we assume exponent is always the largest exponent, // so no need to check/update current.MinExponent } } } private static short FindMinExponentInTree(int[] targetDigits) { SuffixTreeNode current = suffixRoot; foreach(var digit in targetDigits) { if (current == null || current.Children == null) return -1; current = current.Children[digit]; } if (current == null) return -1; return current.MinExponent; } private static int[] ToDigitArray(ulong n) { if (n == 0) return new int[] { 0 }; var digits = new List<int>(); for (; n != 0; n /= 10) digits.Add((int)(n % 10)); var arr = digits.ToArray(); Array.Reverse(arr); return arr; } private static void DoubleDigits(List<int> digits) { bool carry = false; for (int i = digits.Count - 1; i >= 0; i--) { int d = digits [i] * 2; if (carry) d++; if (d >= 10) { d -= 10; carry = true; } else { carry = false; } digits [i] = d; } if (carry) digits.Insert (0, 1); } private class SuffixTreeNode { public short MinExponent; public SuffixTreeNode[] Children; } }