Anonymous user
Minimum positive multiple in base 10 using only 0 and 1: Difference between revisions
Minimum positive multiple in base 10 using only 0 and 1 (view source)
Revision as of 15:47, 8 June 2021
, 2 years ago→{{header|Nim}}
Line 1,461:
A004290(909) = 1011110111111111168 = 909 * 1112332355457768 <-- error
A004290(999) = 1.1000000001001e+19 = 999 * 11011011012013022 <-- error</pre>
=={{header|Nim}}==
{{trans|Phix}}
{{libheader|bignum}}
As in the Phix solution the big integer library is only used to check the result and compute the factor.
<lang Nim>import sequtils, strformat, strutils, times
import bignum
func b10(n: int64): string =
doAssert n > 0, "Argument must be positive."
if n == 1: return "1"
var pow, val = newSeq[int64](n + 1)
var ten = 1i64
for x in 1i64..val.high:
val[x] = ten
for i in 0..n:
if pow[i] != 0 and pow[i] != x:
let k = (ten + i) mod n
if pow[k] == 0: pow[k] = x
if pow[ten] == 0: pow[ten] = x
ten = 10 * ten mod n
if pow[0] != 0: break
if pow[0] == 0:
raise newException(ValueError, "Can’t do it!")
# Build result string.
var x = n
var count = 0'i64
while x != 0:
let pm = pow[x mod n]
if count > pm:
result.add repeat('0', count - pm)
count = pm - 1
result.add '1'
x = (n + x - val[pm]) mod n
result.add repeat('0', count)
const Data = toSeq(1..10) & toSeq(95..105) &
@[297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878]
let t0 = cpuTime()
for val in Data:
let res = b10(val)
let m = newInt(res)
if m mod val != 0: echo &"Wrong result for {val}."
else: echo &"{val:4} × {m div val:<24} = {res}"
echo &"Time: {cpuTime() - t0:.3f} s"</lang>
{{out}}
<pre> 1 × 1 = 1
2 × 5 = 10
3 × 37 = 111
4 × 25 = 100
5 × 2 = 10
6 × 185 = 1110
7 × 143 = 1001
8 × 125 = 1000
9 × 12345679 = 111111111
10 × 1 = 10
95 × 1158 = 110010
96 × 115625 = 11100000
97 × 114433 = 11100001
98 × 112245 = 11000010
99 × 1122334455667789 = 111111111111111111
100 × 1 = 100
101 × 1 = 101
102 × 9805 = 1000110
103 × 107767 = 11100001
104 × 9625 = 1001000
105 × 962 = 101010
297 × 3740778151889263 = 1111011111111111111
576 × 192901234375 = 111111111000000
594 × 18703890759446315 = 11110111111111111110
891 × 1247038284075321 = 1111111111111111011
909 × 1112333455567779 = 1011111111111111111
999 × 111222333444555666777889 = 111111111111111111111111111
1998 × 556111667222778333889445 = 1111111111111111111111111110
2079 × 481530111164555609 = 1001101101111111111111
2251 × 44913861 = 101101101111
2277 × 4879275850290343 = 11110111111111111011
2439 × 4100082415379299344449 = 10000101011110111101111111
2997 × 370740777814851888925963 = 1111110111111111111111111111
4878 × 20500412076896496722245 = 100001010111101111011111110
Time: 0.005 s</pre>
=={{header|Pascal}}==
| |||