Hidden Squares

June 2, 2020

This is easy:

(define (square? n)
  (let ((s (isqrt n)))
    (= n (* s s))))
(define (k-squares k ds)
  (if (< (length ds) k) (list)
    (let ((n (undigits (take k ds))))
      (if (square? n)
          (cons n (k-squares k (cdr ds)))
          (k-squares k (cdr ds))))))
(define (hidden-squares n)
  (let* ((ds (digits n)) (len (length ds)))
    (let loop ((k 1) (hs (list)))
      (if (< len k) (unique = (sort < hs))
        (loop (+ k 1) (append (k-squares k ds) hs))))))

And here is the example:

> (hidden-squares 1625649)
(1 4 9 16 25 49 64 256 625)

You can run the program at https://ideone.com/9Q3suE.

Pages: 1 2

6 Responses to “Hidden Squares”

  1. James Curtis-Smith said

    perl -e ‘print “@{[grep { $ARGV[0]=~/$/ } map { $*$_ } 1..sqrt($ARGV[0]) ]}\n”;’ 1625649

  2. James Curtis-Smith said

    Try again – this time without letting wordpress mess up the formatting…

    perl -e ‘print “@{[grep { $ARGV[0]=~/$/ } map { $*$_ } 1..sqrt($ARGV[0]) ]}\n”;’ 1625649
    
  3. Daniel said

    @programmingpraxis, your solution errors when there is a zero in the number, seemingly from the isqrt function.

  4. Daniel said

    Here’s a solution in Python. The program skips the nested loop in some cases where a candidate cannot possibly be square. An online search suggests additional properties of squares in base 10 that can be utilized to narrow the search further (not implemented in my solution).

    def isqrt(n):
        assert n >= 0
        if n == 0: return 0
        x = n
        while True:
            y = (x + (n // x)) // 2
            if y - x in (0, 1): return x
            x = y
    
    def hidden_squares(n):
        result = set()
        string = str(n)
        for end in range(len(string) - 1, -1, -1):
            if string[end] in ('2', '3', '7', '8'):
                continue
            if end > 0 and string[end] == '5' and string[end - 1] != '2':
                continue
            if end > 0 and string[end] == '0' and string[end - 1] != '0':
                result.add(0)
                continue
            for start in range(end + 1):
                x = int(string[start:end + 1])
                y = isqrt(x)
                if y * y == x:
                    result.add(x)
        return sorted(list(result))
    
    
    print(hidden_squares(1625649))
    print(hidden_squares(162500649))
    
    import random
    random.seed(0)
    digits = 600
    x = int(''.join([str(random.randint(0, 10)) for _ in range(digits)]))
    print(hidden_squares(x))
    

    Output:

    [1, 4, 9, 16, 25, 49, 64, 256, 625]
    [0, 1, 4, 9, 16, 25, 49, 64, 625, 2500, 62500]
    [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 196, 225, 256, 361, 400, 484, 676, 729, 784, 841, 900, 961, 1089, 1764, 7921, 11025, 82369, 96100, 3010225]
    
  5. Larry Lee said

    A naive implementation in Haskell in which I generate a list of candidate squares and then filter them based on the digits given in the argument:

    hiddenSqrs :: Int -> [Int]
    hiddenSqrs n = filterSqrs n $ getSqrs 0
    
      where
        getSqrs :: Int -> [(Int, Int)]
        getSqrs m
          | m^2 <= n  = (m^2, m^2):(getSqrs $ m + 1)
          | otherwise = []
    
        filterSqrs :: Int -> [(Int, Int)] -> [Int]
        filterSqrs _ [] = []
        filterSqrs m pending
          | m == 0    = []
          | otherwise =
            let (cleared, pendingNext)
                  = foldl
                      (\(cleared, pendingNext) (x, y) ->
                        let digit = mod m 10 in
                        if y == digit
                          then (x:cleared, pendingNext)
                          else (cleared, (if mod y 10 == digit
                                           then (x, div y 10)
                                           else (x, y)):pendingNext))
                      ([], [])
                      pending in
            cleared ++ (filterSqrs (div m 10) pendingNext)
    
  6. Larry Lee said
    hiddenSqrs :: Int -> [Int]
    hiddenSqrs n = filterSqrs n $ getSqrs 0
    
      where
        getSqrs :: Int -> [(Int, Int)]
        getSqrs m
          | m^2 <= n  = (m^2, m^2):(getSqrs $ m + 1)
          | otherwise = []
    
        filterSqrs :: Int -> [(Int, Int)] -> [Int]
        filterSqrs _ [] = []
        filterSqrs m pending
          | m == 0    = []
          | otherwise =
            let (cleared, pendingNext)
                  = foldl
                      (\(cleared, pendingNext) (x, y) ->
                        let digit = mod m 10 in
                        if y == digit
                          then (x:cleared, pendingNext)
                          else (cleared, (if mod y 10 == digit
                                           then (x, div y 10)
                                           else (x, y)):pendingNext))
                      ([], [])
                      pending in
            cleared ++ (filterSqrs (div m 10) pendingNext)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: