/
main.go
85 lines (64 loc) · 1.82 KB
/
main.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main
import (
"log"
"os"
"strconv"
"github.com/TomasCruz/projecteuler"
)
/*
Problem 40; Champernowne's constant
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021...
It can be seen that the 12th digit of the fractional part is 1.
If dn represents the nth digit of the fractional part, find the value of the following expression.
d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
*/
func main() {
var limit int
if len(os.Args) > 1 {
limit64, err := strconv.ParseInt(os.Args[1], 10, 64)
if err != nil {
log.Fatal("bad argument")
}
limit = int(limit64)
} else {
limit = 6
}
projecteuler.Timed(calc, limit)
}
func calc(args ...interface{}) (result string, err error) {
limit := args[0].(int)
// digitNumbers are counts of numbers with n digits, i.e. of numbers [10^(n-1), 10^n),
// i.e. digitNumbers[n] = 10^n - 10^(n-1)
// digitNumbers[0]=0, digitNumbers[1]=9 (10^0==1..10), digitNumbers[2]=90 (10^1..10^2), digitNumbers[3]=900
digitNumbers := []int{0, 9, 90, 900, 9000, 90000, 900000}
// digitsUsed[n] is count of digits used for numbers of up to n digits,
// i.e. digitsUsed[2] = 0*0 + 9*1 + 90*2 = 189
digitsUsed := make([]int, len(digitNumbers))
for i := 1; i < len(digitNumbers); i++ {
digitsUsed[i] = digitsUsed[i-1] + digitNumbers[i]*i
}
pow := 2
powered := 100
n := 1
for pow <= limit {
n *= d(powered, digitNumbers, digitsUsed)
pow++
powered *= 10
}
result = strconv.Itoa(n)
return
}
func d(n int, digitNumbers []int, digitsUsed []int) (digit int) {
i := 1
for n > digitsUsed[i] {
i++
}
// i is now number of digits of number containing d(n)
n -= digitsUsed[i-1]
number := digitNumbers[i]/9 + n/i
n -= (n / i) * i
dn := projecteuler.NewDigitalNumber(number)
digit = int(dn.Digits()[i-n])
return
}