// oeis.org/A247665 // Russ Cox // October 8, 2014 // // Generate A247665 using a modified prime sieve. package main import ( "bufio" "fmt" "os" ) const Max = 100000000 var primes []int // primes up to Max var seq []int32 // sequence var sieve []int32 // sieve saying which numbers can appear in the next entry; sieve[i] == 0 means i can appear var stdout = bufio.NewWriter(os.Stdout) func main() { defer stdout.Flush() sieve = make([]int32, Max) for x := 2; x < Max; x++ { if sieve[x] > 0 { continue } primes = append(primes, x) for y := x * 2; y < Max; y += x { sieve[y] = 1 } } for i := range sieve { sieve[i] = 0 } x := 2 // where to start looking in the sieve for the next entry Search: for { if len(seq)%2 == 0 && len(seq) > 0 { factor(int(seq[len(seq)/2-1]), func(f int) { for g := f; g < Max; g += f { sieve[g]-- if sieve[g] == 0 && g < x { x = g } } }) } for ; ; x++ { if x >= Max { return } if sieve[x] == 0 { fmt.Fprintf(stdout, "%d %d\n", len(seq)+1, x) seq = append(seq, int32(x)) factor(x, func(f int) { for g := f; g < Max; g += f { sieve[g]++ } }) sieve[x]++ // will never be 0 again continue Search } } } } func factor(x int, f func(int)) { for _, p := range primes { if p*p > x { break } if x%p == 0 { f(p) for x%p == 0 { x /= p } } } if x != 1 { f(x) } }