#!/bin/env tclsh

# Generates the b-file of A255577 to standard out

# Left-pad with 0's to minimum length
proc "pad" {str min} {
  set len [string length $str]
  if {$len < $min} {
    return "[string repeat 0 [expr {$min - $len}]]$str"
  } else {
    return $str
  }
}

# Return (last * n) % log, left-padded with 0's
proc "nextPower" {last n log} {
  set str [expr {wide($last) * $n}]
  return [pad [string range $str [expr {[string length $str] - $log}] end] $log]
}

# Return true if n is in the sequence (n^k has n as its least
# significant digit(s) for some integer k > 1, and n is not
# coprime with 10)
# PRE: log = floor(log10(n))+1 (pre-calculated for efficiency)
# 
# Generate n^k and store in an array mask(n^k % 10^log) -> (k-1). Once
# the same digits are seen a second time, they will cycle an we can stop.
# Iff those digits = n then return true
proc "isInSequence" {n log} {
  array set mask {}
  set last 1
  for {set k_minus1 0} {true} {incr k_minus1} {
    set trimmed [string trimleft $last 0]
    if {$trimmed == ""} {
      array unset mask
      return false
    }
    set last [nextPower $trimmed $n $log]
    if {[info exists mask($last)]} {
      set result [expr {$mask($last) == 0}]
      array unset mask
      return $result
    }
    set mask($last) $k_minus1
  }
} 

set last [list 2 4 5 6 8]

proc getCandidates {last log} {
  set candidates [list]
  set log_minus1 [expr {$log-1}]
  for {set i 1} {$i < 10} {incr i} {
    foreach c $last {
      set c [pad $c $log_minus1]
      lappend candidates "$i$c"
    }
  }
  return $candidates
}

set idx 0
foreach n $last {
  puts "[incr $idx] $n"
}

for {set log 2} {$idx <= 1000000} {incr log} {
  set candidates [getCandidates $last $log]
  foreach n $candidates {
    if {[isInSequence $n $log]} {
      puts "[incr $idx] $n"
      lappend last $n
    }
  }
}