Knuth's Monotonic Squares

Ruby
  • non-decreasing squares have infinite patterns
# Knuth's Monotonic Squares
# n and n^2 have non-decreasing digits
def digit(n, i)
  (n/10**i)%10
end

def nondec?(n)
  i = n.to_s.length - 1
  i == 0 || digit(n, i) <= digit(n, i-1) && nondec?(n%10**i)
end

kms = (1..9999).inject([]) do |k, n| 
  nondec?(n) && nondec?(n**2)? k << [n, n**2]: k
end

[1, 1], [2, 4], [3, 9], [4, 16], [5, 25], [6, 36], [7, 49], 
[12, 144], [13, 169], [15, 225], [16, 256], [17, 289], 
[34, 1156], [35, 1225], [37, 1369], [38, 1444], 
[67, 4489], [116, 13456], [117, 13689], [167, 27889], 
[334, 111556], [335, 112225], [337, 113569], [367, 134689], 
[667, 444889], [1667, 2778889], 
[3334, 11115556], [3335, 11122225], [3337, 11135569], [3367, 11336689],
[3667, 13446889], [6667, 44448889]

See Problem 1 of "A Programming and Problem-Solving-Seminar"

  • strictly-increasing squares are finite
# Strictly-increasing Squares
# n and n^2 have strictly-increasing digits
def digit(n, i)
  (n/10**i)%10
end

def inc?(n)
  i = n.to_s.length - 1
  i == 0 || digit(n, i) < digit(n, i-1) && inc?(n%10**i)
end

sis = (1..9999).inject([]) do |k, n| 
  inc?(n) && inc?(n**2)? k << [n, n**2]: k
end

[1, 1], [2, 4], [3, 9], [4, 16], [5, 25], [6, 36], [7, 49], 
[13, 169], [16, 256], [17, 289], [37, 1369], [367, 134689]