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 00:59, 20 October 2020
, 3 years ago→{{header|F_Sharp|F#}}
(Added Visual Basic .NET version) |
|||
Line 607:
2997 * 370740777814851888925963 = 1111110111111111111111111111
4878 * 20500412076896496722245 = 100001010111101111011111110</pre>
=={{header|D}}==
{{trans|Java}}
<lang d>import std.algorithm;
import std.array;
import std.bigint;
import std.range;
import std.stdio;
void main() {
foreach (n; chain(iota(1, 11), iota(95, 106), only(297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878))) {
auto result = getA004290(n);
writefln("A004290(%d) = %s = %s * %s", n, result, n, result / n);
}
}
BigInt getA004290(int n) {
if (n == 1) {
return BigInt(1);
}
auto L = uninitializedArray!(int[][])(n, n);
foreach (i; 2..n) {
L[0][i] = 0;
}
L[0][0] = 1;
L[0][1] = 1;
int m = 0;
BigInt ten = 10;
BigInt nBi = n;
while (true) {
m++;
if (L[m - 1][mod(-(ten ^^ m), nBi).toInt] == 1) {
break;
}
L[m][0] = 1;
foreach (k; 1..n) {
L[m][k] = max(L[m - 1][k], L[m - 1][mod(BigInt(k) - (10 ^^ m), nBi).toInt]);
}
}
auto r = ten ^^ m;
auto k = mod(-r, nBi);
foreach_reverse (j; 1 .. m) {
assert(j != m);
if (L[j - 1][k.toInt] == 0) {
r += 10 ^^ j;
k = mod(k - (ten ^^ j), nBi);
}
}
if (k == 1) {
r++;
}
return r;
}
BigInt mod(BigInt m, BigInt n) {
auto result = m % n;
if (result < 0) {
result += n;
}
return result;
}</lang>
{{out}}
<pre>A004290(1) = 1 = 1 * 1
A004290(2) = 10 = 2 * 5
A004290(3) = 111 = 3 * 37
A004290(4) = 100 = 4 * 25
A004290(5) = 10 = 5 * 2
A004290(6) = 1110 = 6 * 185
A004290(7) = 1001 = 7 * 143
A004290(8) = 1000 = 8 * 125
A004290(9) = 111111111 = 9 * 12345679
A004290(10) = 10 = 10 * 1
A004290(95) = 110010 = 95 * 1158
A004290(96) = 11100000 = 96 * 115625
A004290(97) = 11100001 = 97 * 114433
A004290(98) = 11000010 = 98 * 112245
A004290(99) = 10003009548742 = 99 * 101040500492
A004290(100) = 100 = 100 * 1
A004290(101) = 101 = 101 * 1
A004290(102) = 1000110 = 102 * 9805
A004290(103) = 11100001 = 103 * 107767
A004290(104) = 1001000 = 104 * 9625
A004290(105) = 101010 = 105 * 962
A004290(297) = 10003009548742 = 297 * 33680166830
A004290(576) = 1003736928710 = 576 * 1742598834
A004290(594) = 10003009548742 = 594 * 16840083415
A004290(891) = 10003009548742 = 891 * 11226722276
A004290(909) = 100004325683654 = 909 * 110015759828
A004290(999) = 1002521176518 = 999 * 1003524701
A004290(1998) = 10003009548742 = 1998 * 5006511285
A004290(2079) = 10003009548742 = 2079 * 4811452404
A004290(2251) = 101101101111 = 2251 * 44913861
A004290(2277) = 10003009548742 = 2277 * 4393065238
A004290(2439) = 1000004325683654 = 2439 * 410005873589
A004290(2997) = 1002521176518 = 2997 * 334508233
A004290(4878) = 1000004325683654 = 4878 * 205002936794</pre>
=={{header|F_Sharp|F#}}==
| |||