// Solution to Project Euler problem 51
// Author: David J. Oftedal.
package main
import fmt "fmt"
import math "math"
//import regexp "regexp"
import strings "strings"
// A count of the number of primes in each family.
var familycount = make(map[string] uint64)
// The smallest prime in each family.
var smallestmember = make(map[string] uint64)
// Add a prime to its families by masking certain combinations of digits.
func findfamilies(prime uint64) {
num := fmt.Sprintf("%d", prime)
// Replace the digits from 1-10 in the string with an X, which
// symbolizes "one or more instances of the same digit".
for i := 0; i <10; i++ {
// Regexp to replace the digit i with X.
j := fmt.Sprintf("%d", i)
tmpnum := strings.Replace(num, j, "X", -1)
// Proceed only if the prime contains at least one X.
if strings.Index(tmpnum, "X") != -1 {
// Count the current variation of prime as part of its family.
// Also see if it's the smallest member of that family.
familycount[tmpnum]++
if smallestmember[tmpnum] == 0 || prime < smallestmember[tmpnum] {
smallestmember[tmpnum] = prime
}
// Find all variations of prime by substituting
// different combinations of the digit.
findallfamilies("", tmpnum, prime, j)
}
}
}
// Find all families where some or all instances of the digit are masked by X.
// numstart is the part of the number in which no further changes may be made.
// numend is the part of the number in which further changes may be made.
func findallfamilies(numstart, numend string, prime uint64, digit string) {
find := strings.Index(numend, "X")
if find == -1 {
return
}
// Generate two new variants of the prime; one with an X replaced by the
// original digit, and one with the next instance retained.
newnum := numstart + numend[0:find] + digit + numend[find+1:]
// Proceed only if the new variant still contains an X.
if strings.Index(newnum, "X") != -1 {
// Count the new variation of prime as part of its family.
// Also see if it's the smallest member of that family.
familycount[newnum]++
if smallestmember[newnum] == 0 || prime < smallestmember[newnum] {
smallestmember[newnum] = prime
}
findallfamilies(numstart+numend[0:find]+digit, numend[find+1:], prime, digit)
// Also find variations created by retaining the digit and
// replacing other instances of it.
findallfamilies(numstart+numend[0:find+1], numend[find+1:], prime, digit)
}
}
// Count the number of digits in base 10.
func digits(n uint64) uint64 {
if n == 0 {
return 1
}
return uint64(math.Floor(math.Log10(float64(n))))+1
}
// Find the smallest prime that's part of an eight-prime family that has certain
// digits replaced with the a common digit.
func main() {
// Generate the primes less than 1000000 by eliminating non-primes.
primes := make([]uint64, 0)
for i := uint64(2); ; i++ {
// If p is divisible by any smaller prime, it's not prime.
s := uint64(math.Sqrt(float64(i)))
for _, p := range primes {
if(p > s) { break; }
if i % p == 0 {
goto notprime
}
}
// Otherwise, it is prime.
// Add it to all of its prime families.
primes = append(primes, i)
findfamilies(i)
notprime:
// On every 9th, 99th, 999th, etc. iteration, see if there are
// any prime families with exactly eight members.
if digits(i+1) > digits(i) {
for family, count := range familycount {
if count == 8 {
fmt.Printf("The prime family %s has %d members. The smallest member is %d.\n", family, count, smallestmember[family])
return
}
}
}
}
}