#!/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 } } }