Minimum positive multiple in base 10 using only 0 and 1
Every positive integer has infinite base 10 multiples that only use the digits 0 and 1. The goal of this task is to find and display the minimum multiple that has these properties.
Minimum positive multiple in base 10 using only 0 and 1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
This is simple to do, but can be challenging to do efficiently.
To avoid repeating long, unwieldy phrases, the operation "minimum positive multiple of a positive integer n in base 10 that only uses the digits 0 and 1" will hereafter be referred to as "B10".
- Task
Write a routine to find the B10 of a given integer.
E.G.
n B10 n × multiplier
1 1 ( 1 × 1 )
2 10 ( 2 × 5 )
7 1001 ( 7 x 143 )
9 111111111 ( 9 x 12345679 )
10 10 ( 10 x 1 )
and so on.
Use the routine to find and display here, on this page, the B10 value for:
1 through 10, 95 through 105, 297, 576, 594, 891, 909, 999
Optionally find B10 for:
1998, 2079, 2251, 2277
Stretch goal; find B10 for:
2439, 2997, 4878
There are many opportunities for optimizations, but avoid using magic numbers as much as possible. If you do use magic numbers, explain briefly why and what they do for your implementation.
- See also
ALGOL 68
Based on a translation of Rick Heylen's C in the 'Binary' Puzzle link on the OIES site. <lang algol68>BEGIN
# returns B10 for the specified n or -1 if it cannot be found #
# based on Rick Heylen's C program linked from the OEIS site #
PROC find b10 = ( INT n )LONG INT:
IF n < 1 THEN -1
ELIF n = 1 THEN 1
ELSE
[ 0 : n ]LONG INT pow, val;
INT x, ten;
LONG INT count;
INT num = n;
FOR i FROM 0 TO n - 1 DO pow[ i ] := val[ i ] := 0 OD;
count := 0;
ten := 1;
x := 1;
WHILE x < n
AND BEGIN val[ x ] := ten;
FOR j FROM 0 TO n- 1 DO
IF pow[ j ] /= 0 THEN
IF INT j plus ten mod num = ( j + ten ) MOD num;
pow[ j plus ten mod num ] = 0
THEN
IF pow[ j ] /= x THEN pow[ j plus ten mod num ] := x FI
FI
FI
OD;
IF pow[ ten ] = 0 THEN pow[ ten ] := x FI;
ten *:= 10 MODAB num;
pow[ 0 ] = 0
END
DO
x +:= 1
OD;
x := num;
IF pow[ 0 ] = 0 THEN - 1 # couldn't find B10 #
ELSE
LONG INT result := 0;
WHILE x /= 0 DO
WHILE ( count -:= 1 ) > pow[ x MOD num ] - 1 DO result *:= 10 OD;
count := pow [ x MOD num ] -1;
result *:= 10 +:= 1;
x := SHORTEN ( num + x - val[ SHORTEN pow[ x MOD num ] ] ) MOD num
OD;
WHILE count > 0 DO result *:= 10 ; count -:= 1 OD;
result
FI
FI # find B10 # ;
# outputs B10 for the specified n #
PROC show b10 = ( INT n )VOID:
IF LONG INT b10 = find b10( n );
b10 < 1
THEN print( ( "Cannot find B10 for: ", whole( n, 0 ), newline ) )
ELSE
# found B10(n) #
print( ( whole( n, -6 ), ": ", whole( b10, -32 ), " = ", whole( n, -6 ), " * ", whole( b10 OVER n, 0 ), newline ) )
FI;
# task test cases #
FOR n FROM 1 TO 10 DO show b10( n ) OD;
FOR n FROM 95 TO 105 DO show b10( n ) OD;
[]INT tests = ( 297, 576, 594, 891, 909, 999
, 1998, 2079, 2251, 2277
, 2439, 2997, 4878
);
FOR n FROM LWB tests TO UPB tests DO show b10( tests[ n ] ) OD
END </lang>
- Output:
1: 1 = 1 * 1
2: 10 = 2 * 5
3: 111 = 3 * 37
4: 100 = 4 * 25
5: 10 = 5 * 2
6: 1110 = 6 * 185
7: 1001 = 7 * 143
8: 1000 = 8 * 125
9: 111111111 = 9 * 12345679
10: 10 = 10 * 1
95: 110010 = 95 * 1158
96: 11100000 = 96 * 115625
97: 11100001 = 97 * 114433
98: 11000010 = 98 * 112245
99: 111111111111111111 = 99 * 1122334455667789
100: 100 = 100 * 1
101: 101 = 101 * 1
102: 1000110 = 102 * 9805
103: 11100001 = 103 * 107767
104: 1001000 = 104 * 9625
105: 101010 = 105 * 962
297: 1111011111111111111 = 297 * 3740778151889263
576: 111111111000000 = 576 * 192901234375
594: 11110111111111111110 = 594 * 18703890759446315
891: 1111111111111111011 = 891 * 1247038284075321
909: 1011111111111111111 = 909 * 1112333455567779
999: 111111111111111111111111111 = 999 * 111222333444555666777889
1998: 1111111111111111111111111110 = 1998 * 556111667222778333889445
2079: 1001101101111111111111 = 2079 * 481530111164555609
2251: 101101101111 = 2251 * 44913861
2277: 11110111111111111011 = 2277 * 4879275850290343
2439: 10000101011110111101111111 = 2439 * 4100082415379299344449
2997: 1111110111111111111111111111 = 2997 * 370740777814851888925963
4878: 100001010111101111011111110 = 4878 * 20500412076896496722245
C
Compiled using gcc for the 128 bit integer type <lang c>#include <stdbool.h>
- include <stdint.h>
- include <stdio.h>
- include <stdlib.h>
__int128 imax(__int128 a, __int128 b) {
if (a > b) {
return a;
}
return b;
}
__int128 ipow(__int128 b, __int128 n) {
__int128 res;
if (n == 0) {
return 1;
}
if (n == 1) {
return b;
}
res = b;
while (n > 1) {
res *= b;
n--;
}
return res;
}
__int128 imod(__int128 m, __int128 n) {
__int128 result = m % n;
if (result < 0) {
result += n;
}
return result;
}
bool valid(__int128 n) {
if (n < 0) {
return false;
}
while (n > 0) {
int r = n % 10;
if (r > 1) {
return false;
}
n /= 10;
}
return true;
}
__int128 mpm(const __int128 n) {
__int128 *L; __int128 m, k, r, j;
if (n == 1) {
return 1;
}
L = calloc(n * n, sizeof(__int128));
L[0] = 1;
L[1] = 1;
m = 0;
while (true) {
m++;
if (L[(m - 1) * n + imod(-ipow(10, m), n)] == 1) {
break;
}
L[m * n + 0] = 1;
for (k = 1; k < n; k++) {
L[m * n + k] = imax(L[(m - 1) * n + k], L[(m - 1) * n + imod(k - ipow(10, m), n)]);
}
}
r = ipow(10, m); k = imod(-r, n);
for (j = m - 1; j >= 1; j--) {
if (L[(j - 1) * n + k] == 0) {
r = r + ipow(10, j);
k = imod(k - ipow(10, j), n);
}
}
if (k == 1) {
r++;
}
return r / n;
}
void print128(__int128 n) {
char buffer[64]; // more then is needed, but is nice and round; int pos = (sizeof(buffer) / sizeof(char)) - 1; bool negative = false;
if (n < 0) {
negative = true;
n = -n;
}
buffer[pos] = 0;
while (n > 0) {
int rem = n % 10;
buffer[--pos] = rem + '0';
n /= 10;
}
if (negative) {
buffer[--pos] = '-';
}
printf(&buffer[pos]);
}
void test(__int128 n) {
__int128 mult = mpm(n);
if (mult > 0) {
print128(n);
printf(" * ");
print128(mult);
printf(" = ");
print128(n * mult);
printf("\n");
} else {
print128(n);
printf("(no solution)\n");
}
}
int main() {
int i;
// 1-10 (inclusive)
for (i = 1; i <= 10; i++) {
test(i);
}
// 95-105 (inclusive)
for (i = 95; i <= 105; i++) {
test(i);
}
test(297);
test(576);
test(594); // needs a larger number type (64 bits signed)
test(891);
test(909);
test(999); // needs a larger number type (87 bits signed)
// optional test(1998); test(2079); test(2251); test(2277);
// stretch test(2439); test(2997); test(4878);
return 0;
}</lang>
- Output:
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
C#
Translated from the C code for the 'Binary' Puzzle algorithm, from the OEIS link. Note that since this task asks for a maximum of 28 digits for "B10", that only a 32 bit integer is required, even though the original code uses 64 bit integers. Not a huge point, but performance is noticeably improved.
Since C# has a decimal type, it can be used instead of an external 128 bit integer package to compute the multiplier.
<lang csharp>using System; using System.Linq; using System.Collections.Generic; using static System.Console;
class Program {
static string fmt = "{0,4} * {1,24} = {2,-28}\n";
static void B10(int n) { if (n <= 1) return;
int[] pow = new int[++n], val = new int[n--];
int count = 0, ten = 1, x = 1; for (; x <= n; x++) {
val[x] = ten; for (int j = 0; j <= n; j++)
if (pow[j] != 0 && pow[(j + ten) % n] == 0 && pow[j] != x)
pow[(j + ten) % n] = x; if (pow[ten] == 0) pow[ten] = x;
ten = (10 * ten) % n; if (pow[0] != 0) { x = n;
string s = ""; while (x != 0) { int p = pow[x % n];
if (count > p) s += new string('0', count - p);
count = p - 1; s += "1"; x = (n + x - val[p]) % n; }
if (count > 0) s += new string('0', count);
Write(fmt, n, decimal.Parse(s) / n, s);
return; } } Write("Can't do it!"); }
static void Main(string[] args) {
var st = DateTime.Now; List<int> m = new List<int> {
297,576,594,891,909,999,1998,2079,2251,2277,2439,2997,4878};
Write(fmt, "n", "multiplier", "B10");
WriteLine(new string('-', 62)); Write(fmt, 1, 1, 1);
for (int n = 1; n <= m.Last(); n++)
if (n <= 10 || n >= 95 && n <= 105 || m.Contains(n))
B10(n); WriteLine("\nTook {0}ms",
(DateTime.Now - st).TotalMilliseconds); }
}</lang>
- Output:
n * multiplier = B10 -------------------------------------------------------------- 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 Took 10.3014ms
Timing from tio.run
C++
<lang cpp>#include <iostream>
- include <vector>
__int128 imax(__int128 a, __int128 b) {
if (a > b) {
return a;
}
return b;
}
__int128 ipow(__int128 b, __int128 n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return b;
}
__int128 res = b;
while (n > 1) {
res *= b;
n--;
}
return res;
}
__int128 imod(__int128 m, __int128 n) {
__int128 result = m % n;
if (result < 0) {
result += n;
}
return result;
}
bool valid(__int128 n) {
if (n < 0) {
return false;
}
while (n > 0) {
int r = n % 10;
if (r > 1) {
return false;
}
n /= 10;
}
return true;
}
__int128 mpm(const __int128 n) {
if (n == 1) {
return 1;
}
std::vector<__int128> L(n * n, 0); L[0] = 1; L[1] = 1;
__int128 m, k, r, j;
m = 0;
while (true) {
m++;
if (L[(m - 1) * n + imod(-ipow(10, m), n)] == 1) {
break;
}
L[m * n + 0] = 1;
for (k = 1; k < n; k++) {
L[m * n + k] = imax(L[(m - 1) * n + k], L[(m - 1) * n + imod(k - ipow(10, m), n)]);
}
}
r = ipow(10, m); k = imod(-r, n);
for (j = m - 1; j >= 1; j--) {
if (L[(j - 1) * n + k] == 0) {
r = r + ipow(10, j);
k = imod(k - ipow(10, j), n);
}
}
if (k == 1) {
r++;
}
return r / n;
}
std::ostream& operator<<(std::ostream& os, __int128 n) {
char buffer[64]; // more then is needed, but is nice and round; int pos = (sizeof(buffer) / sizeof(char)) - 1; bool negative = false;
if (n < 0) {
negative = true;
n = -n;
}
buffer[pos] = 0;
while (n > 0) {
int rem = n % 10;
buffer[--pos] = rem + '0';
n /= 10;
}
if (negative) {
buffer[--pos] = '-';
}
return os << &buffer[pos];
}
void test(__int128 n) {
__int128 mult = mpm(n);
if (mult > 0) {
std::cout << n << " * " << mult << " = " << (n * mult) << '\n';
} else {
std::cout << n << "(no solution)\n";
}
}
int main() {
int i;
// 1-10 (inclusive)
for (i = 1; i <= 10; i++) {
test(i);
}
// 95-105 (inclusive)
for (i = 95; i <= 105; i++) {
test(i);
}
test(297);
test(576);
test(594); // needs a larger number type (64 bits signed)
test(891);
test(909);
test(999); // needs a larger number type (87 bits signed)
// optional test(1998); test(2079); test(2251); test(2277);
// stretch test(2439); test(2997); test(4878);
return 0;
}</lang>
- Output:
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
D
<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>
- Output:
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
F#
<lang fsharp> // Minimum positive multiple in base 10 using only 0 and 1. Nigel Galloway: March 9th., 2020 let rec fN Σ n i g e l=if l=1||n=1 then Σ+1I else
match (10*i)%l with
g when n=g->Σ+10I**e
|i->match Set.map(fun n->(n+i)%l) g with
ф when ф.Contains n->fN (Σ+10I**e) ((l+n-i)%l) 1 (set[1]) 1 l
|ф->fN Σ n i (Set.unionMany [set[i];g;ф]) (e+1) l
let B10=fN 0I 0 1 (set[1]) 1 List.concat[[1..10];[95..105];[297;576;594;891;909;999;1998;2079;2251;2277;2439;2997;4878]] |>List.iter(fun n->let g=B10 n in printfn "%d * %A = %A" n (g/bigint(n)) g) </lang>
- Output:
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 Real: 00:00:00.454, CPU: 00:00:00.640, GC gen0: 107, gen1: 3, gen2: 1
Factor
This is just the naive implementation, converting the number to a string and checking every character. <lang Factor>
- is-1-or-0 ( char -- ? ) dup CHAR: 0 = [ drop t ] [ CHAR: 1 = ] if ;
- int-is-B10 ( n -- ? ) unparse [ is-1-or-0 ] all? ;
- B10-step ( x x -- x x ? ) dup int-is-B10 [ f ] [ over + t ] if ;
- find-B10 ( x -- x ) dup [ B10-step ] loop nip ;
</lang>
Go
As in the case of the Phix entry, this is based on the C code for Ed Pegg Jr's 'Binary' Puzzle algorithm, linked to by OEIS, which is very quick indeed.
To work out the multipliers for this task, we need to deal with numbers up to 28 digits long. As Go doesn't natively support uint128, I've used a third party library instead which appears to be much quicker than big.Int. <lang go>package main
import (
"fmt" "github.com/shabbyrobe/go-num" "strings" "time"
)
func b10(n int64) {
if n == 1 {
fmt.Printf("%4d: %28s %-24d\n", 1, "1", 1)
return
}
n1 := n + 1
pow := make([]int64, n1)
val := make([]int64, n1)
var count, ten, x int64 = 0, 1, 1
for ; x < n1; x++ {
val[x] = ten
for j := int64(0); j < n1; j++ {
if pow[j] != 0 && pow[(j+ten)%n] == 0 && pow[j] != x {
pow[(j+ten)%n] = x
}
}
if pow[ten] == 0 {
pow[ten] = x
}
ten = (10 * ten) % n
if pow[0] != 0 {
break
}
}
x = n
if pow[0] != 0 {
s := ""
for x != 0 {
p := pow[x%n]
if count > p {
s += strings.Repeat("0", int(count-p))
}
count = p - 1
s += "1"
x = (n + x - val[p]) % n
}
if count > 0 {
s += strings.Repeat("0", int(count))
}
mpm := num.MustI128FromString(s)
mul := mpm.Quo64(n)
fmt.Printf("%4d: %28s %-24d\n", n, s, mul)
} else {
fmt.Println("Can't do it!")
}
}
func main() {
start := time.Now()
tests := [][]int64{{1, 10}, {95, 105}, {297}, {576}, {594}, {891}, {909}, {999},
{1998}, {2079}, {2251}, {2277}, {2439}, {2997}, {4878}}
fmt.Println(" n B10 multiplier")
fmt.Println("----------------------------------------------")
for _, test := range tests {
from := test[0]
to := from
if len(test) == 2 {
to = test[1]
}
for n := from; n <= to; n++ {
b10(n)
}
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</lang>
- Output:
Timing is for an Intel Core i7 8565U machine, using Go 1.14 on Ubuntu 18.04.
n B10 multiplier ---------------------------------------------- 1: 1 1 2: 10 5 3: 111 37 4: 100 25 5: 10 2 6: 1110 185 7: 1001 143 8: 1000 125 9: 111111111 12345679 10: 10 1 95: 110010 1158 96: 11100000 115625 97: 11100001 114433 98: 11000010 112245 99: 111111111111111111 1122334455667789 100: 100 1 101: 101 1 102: 1000110 9805 103: 11100001 107767 104: 1001000 9625 105: 101010 962 297: 1111011111111111111 3740778151889263 576: 111111111000000 192901234375 594: 11110111111111111110 18703890759446315 891: 1111111111111111011 1247038284075321 909: 1011111111111111111 1112333455567779 999: 111111111111111111111111111 111222333444555666777889 1998: 1111111111111111111111111110 556111667222778333889445 2079: 1001101101111111111111 481530111164555609 2251: 101101101111 44913861 2277: 11110111111111111011 4879275850290343 2439: 10000101011110111101111111 4100082415379299344449 2997: 1111110111111111111111111111 370740777814851888925963 4878: 100001010111101111011111110 20500412076896496722245 Took 2.121403ms
Haskell
A direct encoding, without any special optimizations, of the approach described in the Math.StackExchange article referenced in the task description.
<lang haskell>import Data.Bifunctor (bimap) import Data.List (find) import Data.Maybe (isJust)
-- MINIMUM POSITIVE MULTIPLE IN BASE 10 USING ONLY 0 AND 1
b10 :: Integral a => a -> Integer b10 n = read (digitMatch rems sums) :: Integer
where
(_, rems, _, Just (_, sums)) =
until
(\(_, _, _, mb) -> isJust mb)
( \(e, rems, ms, _) ->
let m = rem (10 ^ e) n
newSums =
(m, [m]) :
fmap (bimap (m +) (m :)) ms
in ( succ e,
m : rems,
ms <> newSums,
find
( (0 ==) . flip rem n . fst
)
newSums
)
)
(0, [], [], Nothing)
digitMatch :: Eq a => [a] -> [a] -> String digitMatch [] _ = [] digitMatch xs [] = '0' <$ xs digitMatch (x : xs) yys@(y : ys)
| x /= y = '0' : digitMatch xs yys | otherwise = '1' : digitMatch xs ys
TEST -------------------------
main :: IO () main =
mapM_
( putStrLn
. ( \x ->
let b = b10 x
in justifyRight 5 ' ' (show x)
<> " * "
<> justifyLeft 25 ' ' (show $ div b x)
<> " -> "
<> show b
)
)
( [1 .. 10]
<> [95 .. 105]
<> [297, 576, 594, 891, 909, 999]
)
justifyLeft, justifyRight :: Int -> a -> [a] -> [a] justifyLeft n c s = take n (s <> replicate n c) justifyRight n c = (drop . length) <*> (replicate n c <>)</lang>
- Output:
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
Java
Implementation of algorithm from the OIES site. <lang java> import java.math.BigInteger; import java.util.ArrayList; import java.util.List;
// Title: Minimum positive multiple in base 10 using only 0 and 1
public class MinimumNumberOnlyZeroAndOne {
public static void main(String[] args) {
for ( int n : getTestCases() ) {
BigInteger result = getA004290(n);
System.out.printf("A004290(%d) = %s = %s * %s%n", n, result, n, result.divide(BigInteger.valueOf(n)));
}
}
private static List<Integer> getTestCases() {
List<Integer> testCases = new ArrayList<>();
for ( int i = 1 ; i <= 10 ; i++ ) {
testCases.add(i);
}
for ( int i = 95 ; i <= 105 ; i++ ) {
testCases.add(i);
}
for (int i : new int[] {297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878} ) {
testCases.add(i);
}
return testCases;
}
private static BigInteger getA004290(int n) {
if ( n == 1 ) {
return BigInteger.valueOf(1);
}
int[][] L = new int[n][n];
for ( int i = 2 ; i < n ; i++ ) {
L[0][i] = 0;
}
L[0][0] = 1;
L[0][1] = 1;
int m = 0;
BigInteger ten = BigInteger.valueOf(10);
BigInteger nBi = BigInteger.valueOf(n);
while ( true ) {
m++;
// if L[m-1, (-10^m) mod n] = 1 then break
if ( L[m-1][mod(ten.pow(m).negate(), nBi).intValue()] == 1 ) {
break;
}
L[m][0] = 1;
for ( int k = 1 ; k < n ; k++ ) {
//L[m][k] = Math.max(L[m-1][k], L[m-1][mod(k-pow(10,m), n)]);
L[m][k] = Math.max(L[m-1][k], L[m-1][mod(BigInteger.valueOf(k).subtract(ten.pow(m)), nBi).intValue()]);
}
}
//int r = pow(10,m);
//int k = mod(-pow(10,m), n);
BigInteger r = ten.pow(m);
BigInteger k = mod(r.negate(), nBi);
for ( int j = m-1 ; j >= 1 ; j-- ) {
if ( L[j-1][k.intValue()] == 0 ) {
//r = r + pow(10, j);
//k = mod(k-pow(10, j), n);
r = r.add(ten.pow(j));
k = mod(k.subtract(ten.pow(j)), nBi);
}
}
if ( k.compareTo(BigInteger.ONE) == 0 ) {
r = r.add(BigInteger.ONE);
}
return r;
}
private static BigInteger mod(BigInteger m, BigInteger n) {
BigInteger result = m.mod(n);
if ( result.compareTo(BigInteger.ZERO) < 0 ) {
result = result.add(n);
}
return result;
}
@SuppressWarnings("unused")
private static int mod(int m, int n) {
int result = m % n;
if ( result < 0 ) {
result += n;
}
return result;
}
@SuppressWarnings("unused")
private static int pow(int base, int exp) {
return (int) Math.pow(base, exp);
}
} </lang>
- Output:
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) = 111111111111111111 = 99 * 1122334455667789 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) = 1111011111111111111 = 297 * 3740778151889263 A004290(576) = 111111111000000 = 576 * 192901234375 A004290(594) = 11110111111111111110 = 594 * 18703890759446315 A004290(891) = 1111111111111111011 = 891 * 1247038284075321 A004290(909) = 1011111111111111111 = 909 * 1112333455567779 A004290(999) = 111111111111111111111111111 = 999 * 111222333444555666777889 A004290(1998) = 1111111111111111111111111110 = 1998 * 556111667222778333889445 A004290(2079) = 1001101101111111111111 = 2079 * 481530111164555609 A004290(2251) = 101101101111 = 2251 * 44913861 A004290(2277) = 11110111111111111011 = 2277 * 4879275850290343 A004290(2439) = 10000101011110111101111111 = 2439 * 4100082415379299344449 A004290(2997) = 1111110111111111111111111111 = 2997 * 370740777814851888925963 A004290(4878) = 100001010111101111011111110 = 4878 * 20500412076896496722245
Julia
Uses the iterate in base 2, check for a multiple in base 10 method. Still slow but gets time below 1 minute by calculating the base 10 number within the same loop as the one that finds the base 2 digits. <lang julia>function B10(n)
for i in Int128(1):typemax(Int128)
q, b10, place = i, zero(Int128), one(Int128)
while q > 0
q, r = divrem(q, 2)
if r != 0
b10 += place
end
place *= 10
end
if b10 % n == 0
return b10
end
end
end
for n in [1:10; 95:105; [297, 576, 891, 909, 1998, 2079, 2251, 2277, 2439, 2997, 4878]]
i = B10(n)
println("B10($n) = $n * $(div(i, n)) = $i")
end
</lang>
- Output:
B10(1) = 1 * 1 = 1 B10(2) = 2 * 5 = 10 B10(3) = 3 * 37 = 111 B10(4) = 4 * 25 = 100 B10(5) = 5 * 2 = 10 B10(6) = 6 * 185 = 1110 B10(7) = 7 * 143 = 1001 B10(8) = 8 * 125 = 1000 B10(9) = 9 * 12345679 = 111111111 B10(10) = 10 * 1 = 10 B10(95) = 95 * 1158 = 110010 B10(96) = 96 * 115625 = 11100000 B10(97) = 97 * 114433 = 11100001 B10(98) = 98 * 112245 = 11000010 B10(99) = 99 * 1122334455667789 = 111111111111111111 B10(100) = 100 * 1 = 100 B10(101) = 101 * 1 = 101 B10(102) = 102 * 9805 = 1000110 B10(103) = 103 * 107767 = 11100001 B10(104) = 104 * 9625 = 1001000 B10(105) = 105 * 962 = 101010 B10(297) = 297 * 3740778151889263 = 1111011111111111111 B10(576) = 576 * 192901234375 = 111111111000000 B10(891) = 891 * 1247038284075321 = 1111111111111111011 B10(909) = 909 * 1112333455567779 = 1011111111111111111 B10(1998) = 1998 * 556111667222778333889445 = 1111111111111111111111111110 B10(2079) = 2079 * 481530111164555609 = 1001101101111111111111 B10(2251) = 2251 * 44913861 = 101101101111 B10(2277) = 2277 * 4879275850290343 = 11110111111111111011 B10(2439) = 2439 * 4100082415379299344449 = 10000101011110111101111111 B10(2997) = 2997 * 370740777814851888925963 = 1111110111111111111111111111 B10(4878) = 4878 * 20500412076896496722245 = 100001010111101111011111110
Puzzle algorithm version
<lang julia>function B10(n)
n == 1 && return one(Int128)
num, count, ten = n + 1, 0, 1
val, pow = zeros(Int, num), zeros(Int, num)
for i in 1:n
val[i + 1] = ten
for j in 1:num
k = (j + ten - 1) % n + 1
if pow[j] != 0 && pow[k] == 0 && pow[j] != i
pow[k] = i
end
end
if pow[ten + 1] == 0
pow[ten + 1] = i
end
ten = (10 * ten) % n
(pow[1] != 0) && break
end
res, i = "", n
while i != 0
pm = pow[i % n + 1]
if count > pm
res *= "0"^(count - pm)
end
count = pm - 1
res *= "1"
i = (n + i - val[pm + 1]) % n
end
if count > 0
res *= "0"^count
end
return parse(Int128, res)
end
const tests = [1:10; 95:105; [97, 576, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878, 9999, 2 * 9999]]
@time for n in tests
i = B10(n)
println("B10($n) = $n * $(div(i, n)) = $i")
end
</lang>
- Output:
B10(1) = 1 * 1 = 1 B10(2) = 2 * 5 = 10 B10(3) = 3 * 37 = 111 B10(4) = 4 * 25 = 100 B10(5) = 5 * 2 = 10 B10(6) = 6 * 185 = 1110 B10(7) = 7 * 143 = 1001 B10(8) = 8 * 125 = 1000 B10(9) = 9 * 12345679 = 111111111 B10(10) = 10 * 1 = 10 B10(95) = 95 * 1158 = 110010 B10(96) = 96 * 115625 = 11100000 B10(97) = 97 * 114433 = 11100001 B10(98) = 98 * 112245 = 11000010 B10(99) = 99 * 1122334455667789 = 111111111111111111 B10(100) = 100 * 1 = 100 B10(101) = 101 * 1 = 101 B10(102) = 102 * 9805 = 1000110 B10(103) = 103 * 107767 = 11100001 B10(104) = 104 * 9625 = 1001000 B10(105) = 105 * 962 = 101010 B10(97) = 97 * 114433 = 11100001 B10(576) = 576 * 192901234375 = 111111111000000 B10(891) = 891 * 1247038284075321 = 1111111111111111011 B10(909) = 909 * 1112333455567779 = 1011111111111111111 B10(999) = 999 * 111222333444555666777889 = 111111111111111111111111111 B10(1998) = 1998 * 556111667222778333889445 = 1111111111111111111111111110 B10(2079) = 2079 * 481530111164555609 = 1001101101111111111111 B10(2251) = 2251 * 44913861 = 101101101111 B10(2277) = 2277 * 4879275850290343 = 11110111111111111011 B10(2439) = 2439 * 4100082415379299344449 = 10000101011110111101111111 B10(2997) = 2997 * 370740777814851888925963 = 1111110111111111111111111111 B10(4878) = 4878 * 20500412076896496722245 = 100001010111101111011111110 B10(9999) = 9999 * 11112222333344445555666677778889 = 111111111111111111111111111111111111 B10(19998) = 19998 * 55561111666722227778333388894445 = 1111111111111111111111111111111111110 0.054239 seconds (1.67 k allocations: 917.734 KiB)
Kotlin
<lang scala>import java.math.BigInteger
fun main() {
for (n in testCases) {
val result = getA004290(n)
println("A004290($n) = $result = $n * ${result / n.toBigInteger()}")
}
}
private val testCases: List<Int>
get() {
val testCases: MutableList<Int> = ArrayList()
for (i in 1..10) {
testCases.add(i)
}
for (i in 95..105) {
testCases.add(i)
}
for (i in intArrayOf(297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878)) {
testCases.add(i)
}
return testCases
}
private fun getA004290(n: Int): BigInteger {
if (n == 1) {
return BigInteger.ONE
}
val arr = Array(n) { IntArray(n) }
for (i in 2 until n) {
arr[0][i] = 0
}
arr[0][0] = 1
arr[0][1] = 1
var m = 0
val ten = BigInteger.TEN
val nBi = n.toBigInteger()
while (true) {
m++
if (arr[m - 1][mod(-ten.pow(m), nBi).toInt()] == 1) {
break
}
arr[m][0] = 1
for (k in 1 until n) {
arr[m][k] = arr[m - 1][k].coerceAtLeast(arr[m - 1][mod(k.toBigInteger() - ten.pow(m), nBi).toInt()])
}
}
var r = ten.pow(m)
var k = mod(-r, nBi)
for (j in m - 1 downTo 1) {
if (arr[j - 1][k.toInt()] == 0) {
r += ten.pow(j)
k = mod(k - ten.pow(j), nBi)
}
}
if (k.compareTo(BigInteger.ONE) == 0) {
r += BigInteger.ONE
}
return r
}
private fun mod(m: BigInteger, n: BigInteger): BigInteger {
var result = m.mod(n)
if (result < BigInteger.ZERO) {
result += n
}
return result
}</lang>
- Output:
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) = 111111111111111111 = 99 * 1122334455667789 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) = 1111011111111111111 = 297 * 3740778151889263 A004290(576) = 111111111000000 = 576 * 192901234375 A004290(594) = 11110111111111111110 = 594 * 18703890759446315 A004290(891) = 1111111111111111011 = 891 * 1247038284075321 A004290(909) = 1011111111111111111 = 909 * 1112333455567779 A004290(999) = 111111111111111111111111111 = 999 * 111222333444555666777889 A004290(1998) = 1111111111111111111111111110 = 1998 * 556111667222778333889445 A004290(2079) = 1001101101111111111111 = 2079 * 481530111164555609 A004290(2251) = 101101101111 = 2251 * 44913861 A004290(2277) = 11110111111111111011 = 2277 * 4879275850290343 A004290(2439) = 10000101011110111101111111 = 2439 * 4100082415379299344449 A004290(2997) = 1111110111111111111111111111 = 2997 * 370740777814851888925963 A004290(4878) = 100001010111101111011111110 = 4878 * 20500412076896496722245
Pascal
Simple brute force by generating all possible base 10 numbers with only 0,1.
Extended to 38 digits by dividing in to two numbers concatenated to Uint128 checking in a loop low values and memorizing the Modulus n and its first occurrence
gmp is only used, to get the multiplier.
Now lightning fast
<lang pascal>program B10_num;
//numbers having only digits 0 and 1 in their decimal representation
//see https://oeis.org/A004290
//Limit of n= 2^19
{$IFDEF FPC} //fpc 3.0.4
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$codealign proc=16}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
sysutils,gmp; //Format
const
Limit = 256*256*8;//8+8+3 Bits aka 19 digits
B10_4 = 10*10*10*10;
B10_5 = 10*B10_4;
B10_9 = B10_5*B10_4;
HexB10 : array[0..15] of NativeUint = (0000,0001,0010,0011,0100,0101,0110,0111,
1000,1001,1010,1011,1100,1101,1110,1111);
var
ModToIdx : array[0..Limit] of Int32; B10ModN : array[0..limit-1] of Uint32; B10 : array of Uint64;
procedure OutOfRange(n:NativeUint); Begin
Writeln(n:7,' -- out of range --');
end;
function ConvB10(n: Uint32):Uint64; //Convert n from binary as if it is Base 10 //limited for Uint64 to 2^20-1= 1048575 ala 19 digits var
fac_B10 : Uint64;
Begin
fac_B10 := 1; result := 0; repeat result += fac_B10*HexB10[n AND 15]; n := n DIV 16; fac_B10 *=B10_4; until n = 0;
end;
procedure InitB10; var
i : NativeUint;
Begin
setlength(B10,Limit); For i := 0 to Limit do b10[i]:= ConvB10(i);
end;
procedure Out_Big(n,h,l:NativeUint); var
num,rest : MPInteger;
Begin
//For Windows gmp ui is Uint32 :-( z_init_set_ui(num,Hi(B10[h])); z_mul_2exp(num,num,32); z_add_ui(num,num,Lo(B10[h])); z_mul_ui(num,num,B10_5);z_mul_ui(num,num,B10_5); z_mul_ui(num,num,B10_5);z_mul_ui(num,num,B10_4);
z_init_set_ui(rest,Hi(B10[l]));
z_mul_2exp(rest,rest,32);
z_add_ui(rest,rest,Lo(B10[l]));
z_add(num,num,rest);
write(Format('%7d %19u%.19u ',[n,B10[h],B10[l]]));
IF z_divisible_ui_p(num,n) then
Begin
z_cdiv_q_ui(num, num,n);
write(z_get_str(10,num));
end;
writeln;
z_clear(rest);
z_clear(num);
end;
procedure Out_Small(i,n: NativeUint); var
value,Mul : Uint64;
Begin
value := B10[i]; mul := value div n; IF mul = 1 then mul := n; writeln(n:7,value:39,' ',mul);
end;
procedure CheckBig_B10(n:NativeUint); var
h,BigMod,h_mod:NativeUint; l : NativeInt;
Begin
BigMod :=(sqr(B10_9)*10) MOD n;
For h := Low(B10ModN)+1 to High(B10ModN) do
Begin
//h_mod+l_mod == n => n- h_mod = l_mod
h_mod := n-(BigMod*B10ModN[h])MOD n;
l := ModToIdx[h_mod];
if l>= 0 then
Begin
Out_Big(n,h,l);
EXIT;
end;
end;
OutOfRange(n);
end;
procedure Check_B10(n:NativeUint); var
pB10 : pUint64; i,value : NativeUint;
begin
B10ModN[0] := 0;
//set all modulus n => 0..N-1 to -1
fillchar(ModToIdx,n*SizeOf(ModToIdx[0]),#255);
ModToIdx[0] := 0;
pB10 := @B10[0];
i := 1;
repeat
value := Uint64(pB10[i]) MOD n;
If value = 0 then
Break;
B10ModN[i] := value;
//memorize the first occurrence
if ModToIdx[value] < 0 then
ModToIdx[value]:= i;
inc(i);
until i > High(B10ModN);
IF i < High(B10ModN) then
Out_Small(i,n)
else
CheckBig_B10(n);
end;
var
n : Uint32;
Begin
InitB10;
writeln('Number':7,'B10':39,' Multiplier');
For n := 1 to 10 do
Check_B10(n);
For n := 95 to 105 do
Check_B10(n);
Check_B10(297); Check_B10(576); Check_B10(891); Check_B10(909); Check_B10( 999); Check_B10(1998); Check_B10(2079); Check_B10(2251); Check_B10(2277); Check_B10(2439); Check_B10(2997); Check_B10(4878); check_B10(9999); check_B10(2*9999); //real 0m0,077s :-)
end.</lang>
- Output:
Number B10 Multiplier
1 1 1
2 10 5
3 111 37
4 100 25
5 10 2
6 1110 185
7 1001 143
8 1000 125
9 111111111 12345679
10 10 10
95 110010 1158
96 11100000 115625
97 11100001 114433
98 11000010 112245
99 111111111111111111 1122334455667789
100 100 100
101 101 101
102 1000110 9805
103 11100001 107767
104 1001000 9625
105 101010 962
297 1111011111111111111 3740778151889263
576 111111111000000 192901234375
891 1111111111111111011 1247038284075321
909 1011111111111111111 1112333455567779
999 111111111111111111111111111 111222333444555666777889
1998 1111111111111111111111111110 556111667222778333889445
2079 1001101101111111111111 481530111164555609
2251 101101101111 44913861
2277 11110111111111111011 4879275850290343
2439 10000101011110111101111111 4100082415379299344449
2997 1111110111111111111111111111 370740777814851888925963
4878 100001010111101111011111110 20500412076896496722245
9999 111111111111111111111111111111111111 11112222333344445555666677778889
19998 1111111111111111111111111111111111110 55561111666722227778333388894445
Perl
Brutish and short
Brute-force code does the task minimum, but slowly (and that even with a short-circuit to avoid calculations for 99, 999) <lang perl>use strict; use warnings; use Math::AnyNum qw(:overload as_bin digits2num);
for my $x (1..10, 95..105, 297, 576, 594, 891, 909, 999) {
my $y;
if ($x =~ /^9+$/) { $y = digits2num([(1) x (9 * length $x)],2) } # all 9's implies all 1's
else { while (1) { last unless as_bin(++$y) % $x } }
printf "%4d: %28s %s\n", $x, as_bin($y), as_bin($y)/$x;
}</lang>
- Output:
1: 1 1 2: 10 5 3: 111 37 4: 100 25 5: 10 2 6: 1110 185 7: 1001 143 8: 1000 125 9: 111111111 12345679 10: 10 1 95: 110010 1158 96: 11100000 115625 97: 11100001 114433 98: 11000010 112245 99: 111111111111111111 1122334455667789 100: 100 1 101: 101 1 102: 1000110 9805 103: 11100001 107767 104: 1001000 9625 105: 101010 962 297: 1111011111111111111 3740778151889263 576: 111111111000000 192901234375 594: 11110111111111111110 18703890759446315 891: 1111111111111111011 1247038284075321 909: 1011111111111111111 1112333455567779 999: 111111111111111111111111111 111222333444555666777889
Schmidt / Heylen
Much faster, while also completing stretch goal.
<lang perl>use strict; use warnings; use Math::AnyNum qw(:overload powmod);
sub B10 {
my($n) = @_; return 0 unless $n;
my @P = (-1) x $n;
for (my $m = 0; $P[0] == -1; ++$m) {
for my $r (0..$n-1) {
next if $P[$r] == -1 or $P[$r] == $m;
for ((powmod(10, $m, $n) + $r) % $n) { $P[$_] = $m if $P[$_] == -1 }
}
for (powmod(10, $m, $n)) { $P[$_] = $m if $P[$_] == -1 }
}
my $R = my $r = 0;
do {
$R += 10**$P[$r];
$r = ($r - powmod(10, $P[$r], $n)) % $n
} while $r > 0;
$R
}
printf "%5s: %28s %s\n", 'Number', 'B10', 'Multiplier';
for my $n (1..10, 95..105, 297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878) {
my $a = B10($n); printf "%6d: %28s %s\n", $n, $a, $a/$n;
}</lang>
- Output:
1: 1 1
2: 10 5
3: 111 37
4: 100 25
5: 10 2
6: 1110 185
7: 1001 143
8: 1000 125
9: 111111111 12345679
10: 10 1
95: 110010 1158
96: 11100000 115625
97: 11100001 114433
98: 11000010 112245
99: 111111111111111111 1122334455667789
100: 100 1
101: 101 1
102: 1000110 9805
103: 11100001 107767
104: 1001000 9625
105: 101010 962
297: 1111011111111111111 3740778151889263
576: 111111111000000 192901234375
594: 11110111111111111110 18703890759446315
891: 1111111111111111011 1247038284075321
909: 1011111111111111111 1112333455567779
999: 111111111111111111111111111 111222333444555666777889
1998: 1111111111111111111111111110 556111667222778333889445
2079: 1001101101111111111111 481530111164555609
2251: 101101101111 44913861
2277: 11110111111111111011 4879275850290343
2439: 10000101011110111101111111 4100082415379299344449
2997: 1111110111111111111111111111 370740777814851888925963
4878: 100001010111101111011111110 20500412076896496722245
Phix
Using the Ed Pegg Jr 'Binary' Puzzle algorithm as linked to by OEIS.
Very fast, finishes near-instantly, only needs/uses gmp to validate the results.
<lang Phix>function b10(integer n)
if n=1 then return "1" end if
integer NUM = n+1, count = 0, ten = 1, x
sequence val = repeat(0,NUM),
pow = repeat(0,NUM)
--
-- Calculate each 10^k mod n, along with all possible sums that can be
-- made from it and the things we've seen before, until we get a 0, eg:
--
-- ten/val[] (for n==7) See pow[], for k
-- 10^0 = 1 mod 7 = 1. Possible sums: 1
-- 10^1 = 10 mod 7 = 3. Possible sums: 1 3 4
-- 10^2 = 10*3 = 30 mod 7 = 2. Possible sums: 1 2 3 4 5 6
-- 10^3 = 10*2 = 20 mod 7 = 6. STOP (6+1 = 7 mod 7 = 0)
--
-- ie since 10^3 mod 7 + 10^0 mod 7 == (6+1) mod 7 == 0, we know that
-- 1001 mod 7 == 0, and we have found that w/o checking every interim
-- value from 11 to 1000 (aside: use binary if counting that range).
--
-- Another example is 10^k mod 9 is 1 for all k. Hence we need to find
-- 9 different ways to generate a 1, before we get a sum (mod 9) of 0,
-- and hence b10(9) is 111111111, ie 10^8+10^7+..+10^0, and obviously
-- 9 iterations is somewhat less than all interims 11..111111110.
--
for x=1 to n do
val[x+1] = ten
for j=1 to NUM do
if pow[j] and pow[j]!=x then -- (j seen, in a prior iteration)
integer k = mod(j-1+ten,n)+1
if not pow[k] then
pow[k]=x -- (k was seen in this iteration)
end if
end if
end for
if not pow[ten+1] then pow[ten+1] = x end if
ten = mod(10*ten,n)
if pow[1] then exit end if
end for
if pow[1]=0 then crash("Can't do it!") end if
--
-- Fairly obviously (for b10(7)) we need the 10^3, then we will need
-- a sum of 1, which first appeared for 10^0, after which we are done.
-- The required answer is therefore 1001, ie 10^3 + 10^0.
--
string res = ""
x = n
while x do
integer pm = pow[mod(x,n)+1]
if count>pm then res &= repeat('0',count-pm) end if
count = pm-1;
res &= '1'
x = mod(n+x-val[pm+1],n)
end while
res &= repeat('0',count)
return res
end function
constant tests = tagset(10)&tagset(105,95)&{297, 576, 891, 909,
999, 1998, 2079, 2251, 2277, 2439, 2997, 4878}
include mpfr.e mpz m10 = mpz_init() atom t0 = time() for i=1 to length(tests) do
integer ti = tests[i]
string r10 = b10(ti)
mpz_set_str(m10,r10,10)
if mpz_fdiv_q_ui(m10,m10,ti)!=0 then r10 &= " ??" end if
printf(1,"%4d * %-24s = %s\n",{ti,mpz_get_str(m10),r10})
end for ?elapsed(time()-t0) </lang>
- Output:
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 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 "0.1s"
Raku
(formerly Perl 6)
Naive, brute force. Simplest thing that could possibly work. Will find any B10 eventually (until you run out of memory or patience) but sloooow, especially for larger multiples of 9.
<lang perl6>say $_ , ': ', (1..*).map( *.base(2) ).first: * %% $_ for flat 1..10, 95..105; # etc.</lang>
Based on Ed Pegg jr.s C code from Mathpuzzlers.com. Similar to Phix and Go entries.
<lang perl6>sub Ed-Pegg-jr (\n) {
return 1 if n == 1;
my ($count, $power-mod-n) = 0, 1;
my @oom-mod-n = 0; # orders of magnitude of 10 mod n
my @dig-mod = 0; # 1 to n + oom mod n
for 1..n -> \i {
@oom-mod-n[i] = $power-mod-n;
for 1..n -> \j {
my \k = (j + $power-mod-n - 1) % n + 1;
@dig-mod[k] = i if @dig-mod[j] and @dig-mod[j] != i and !@dig-mod[k];
}
@dig-mod[$power-mod-n + 1] ||= i;
($power-mod-n *= 10) %= n;
last if @dig-mod[1];
}
my ($b10, $remainder) = , n;
while $remainder {
my $place = @dig-mod[$remainder % n + 1];
$b10 ~= '0' x ($count - $place) if $count > $place;
$count = $place - 1;
$b10 ~= '1';
$remainder = (n + $remainder - @oom-mod-n[$place]) % n;
}
$b10 ~ '0' x $count
}
printf "%5s: %28s %s\n", 'Number', 'B10', 'Multiplier';
for flat 1..10, 95..105, 297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878 {
printf "%6d: %28s %s\n", $_, my $a = Ed-Pegg-jr($_), $a / $_;
}</lang>
- Output:
Number: B10 Multiplier
1: 1 1
2: 10 5
3: 111 37
4: 100 25
5: 10 2
6: 1110 185
7: 1001 143
8: 1000 125
9: 111111111 12345679
10: 10 1
95: 110010 1158
96: 11100000 115625
97: 11100001 114433
98: 11000010 112245
99: 111111111111111111 1122334455667789
100: 100 1
101: 101 1
102: 1000110 9805
103: 11100001 107767
104: 1001000 9625
105: 101010 962
297: 1111011111111111111 3740778151889263
576: 111111111000000 192901234375
594: 11110111111111111110 18703890759446315
891: 1111111111111111011 1247038284075321
909: 1011111111111111111 1112333455567779
999: 111111111111111111111111111 111222333444555666777889
1998: 1111111111111111111111111110 556111667222778333889445
2079: 1001101101111111111111 481530111164555609
2251: 101101101111 44913861
2277: 11110111111111111011 4879275850290343
2439: 10000101011110111101111111 4100082415379299344449
2997: 1111110111111111111111111111 370740777814851888925963
4878: 100001010111101111011111110 20500412076896496722245
REXX
<lang rexx>/*REXX pgm finds minimum pos. integer that's a product of N that only has the digs 0 & 1*/ numeric digits 30; w= length( commas( copies(1, digits()))) /*for formatting numbers.*/ parse arg list if list== then list= 1..10 95..105 297 say center(' N ', 9, "─") center(' B10 ', w, "─") center(' multiplier ', w, "─")
do i=1 for words(list)
z= word(list, i); LO= z; HI= z
if pos(.., z)\==0 then parse var z LO '..' HI
do n=LO to HI; m= B10(n)
say right(commas(n), 9) right(commas(n*m), w) left(commas(m), w)
end /*n*/
end /*i*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do c=length(_)-3 to 1 by -3; _= insert(',', _, c); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ B10: parse arg #; inc= 1; start= 1; L= length(#)
select
when verify(#, 10)==0 then return 1
when verify(#, 9)==0 then do; start=
do k= 1 for 8
start= start || copies(k, L)
end /*k*/
end
when #//2==0 then do; start=5; inc= 5; end
when right(z, 1)==7 then do; start=3; inc= 10; end
otherwise nop
end /*select*/
q= length(start)
if q>digits() then numeric digits q
do m=start by inc until verify(p, 10)==0; p= # * m
end /*m*/
return m</lang>
- output when using the default inputs:
─── N ─── ───────────────── B10 ───────────────── ───────────── multiplier ──────────────
1 1 1
2 10 5
3 111 37
4 100 25
5 10 2
6 1,110 185
7 1,001 143
8 1,000 125
9 111,111,111 12,345,679
10 10 1
95 110,010 1,158
96 11,100,000 115,625
97 11,100,001 114,433
98 11000010 112245
98 11,000,010 112,245
99 111111111111111111 1122334455667789
99 111,111,111,111,111,111 1,122,334,455,667,789
100 100 1
101 101 1
102 1,000,110 9,805
103 11,100,001 107,767
104 1,001,000 9,625
105 101,010 962
297 1,111,011,111,111,111,111 3,740,778,151,889,263
576 111,111,111,000,000 192,901,234,375
594 11,110,111,111,111,111,110 18,703,890,759,446,315
891 1,111,111,111,111,111,011 1,247,038,284,075,321
909 1,011,111,111,111,111,111 1,112,333,455,567,779
999 111,111,111,111,111,111,111,111,111 111,222,333,444,555,666,777,889
Ring
<lang ring> see "working..." + nl see "Minimum positive multiple in base 10 using only 0 and 1:" + nl
limit1 = 1000 limit2 = 111222333444555666777889 plusflag = 0 plus = [297,576,594,891,909,999]
for n = 1 to limit1
if n = 106
plusflag = 1
nplus = 0
loop
ok
lenplus = len(plus)
if plusflag = 1
nplus = nplus + 1
if nplus < lenplus+1
n = plus[nplus]
else
exit
ok
ok
for m = 1 to limit2
flag = 1
prod = n*m
pstr = string(prod)
for p = 1 to len(pstr)
if not(pstr[p] = "0" or pstr[p] = "1")
flag = 0
exit
ok
next
if flag = 1
see "" + n + " * " + m + " = " + pstr + nl
exit
ok
next
if n = 10
n = 94
ok
next
see "done..." + nl </lang>
- Output:
working... Minimum positive multiple in base 10 using only 0 and 1: 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
Ruby
<lang ruby>def mod(m, n)
result = m % n
if result < 0 then
result = result + n
end
return result
end
def getA004290(n)
if n == 1 then
return 1
end
arr = Array.new(n) { Array.new(n, 0) }
arr[0][0] = 1
arr[0][1] = 1
m = 0
while true
m = m + 1
if arr[m - 1][mod(-10 ** m, n)] == 1 then
break
end
arr[m][0] = 1
for k in 1 .. n - 1
arr[m][k] = [arr[m - 1][k], arr[m - 1][mod(k - 10 ** m, n)]].max
end
end
r = 10 ** m
k = mod(-r, n)
(m - 1).downto(1) { |j|
if arr[j - 1][k] == 0 then
r = r + 10 ** j
k = mod(k - 10 ** j, n)
end
}
if k == 1 then
r = r + 1
end
return r
end
testCases = Array(1 .. 10) testCases.concat(Array(95 .. 105)) testCases.concat([297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878]) for n in testCases
result = getA004290(n) print "A004290(%d) = %d = %d * %d\n" % [n, result, n, result / n]
end</lang>
- Output:
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) = 111111111111111111 = 99 * 1122334455667789 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) = 1111011111111111111 = 297 * 3740778151889263 A004290(576) = 111111111000000 = 576 * 192901234375 A004290(594) = 11110111111111111110 = 594 * 18703890759446315 A004290(891) = 1111111111111111011 = 891 * 1247038284075321 A004290(909) = 1011111111111111111 = 909 * 1112333455567779 A004290(999) = 111111111111111111111111111 = 999 * 111222333444555666777889 A004290(1998) = 1111111111111111111111111110 = 1998 * 556111667222778333889445 A004290(2079) = 1001101101111111111111 = 2079 * 481530111164555609 A004290(2251) = 101101101111 = 2251 * 44913861 A004290(2277) = 11110111111111111011 = 2277 * 4879275850290343 A004290(2439) = 10000101011110111101111111 = 2439 * 4100082415379299344449 A004290(2997) = 1111110111111111111111111111 = 2997 * 370740777814851888925963 A004290(4878) = 100001010111101111011111110 = 4878 * 20500412076896496722245
Scala
<lang scala>import scala.collection.mutable.ListBuffer
object MinimumNumberOnlyZeroAndOne {
def main(args: Array[String]): Unit = {
for (n <- getTestCases) {
val result = getA004290(n)
println(s"A004290($n) = $result = $n * ${result / n}")
}
}
def getTestCases: List[Int] = {
val testCases = ListBuffer.empty[Int]
for (i <- 1 to 10) {
testCases += i
}
for (i <- 95 to 105) {
testCases += i
}
for (i <- Array(297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878)) {
testCases += i
}
testCases.toList
}
def getA004290(n: Int): BigInt = {
if (n == 1) {
return 1
}
val L = Array.ofDim[Int](n, n)
for (i <- 2 until n) {
L(0)(i) = 0
}
L(0)(0) = 1
L(0)(1) = 1
var m = 0
val ten = BigInt(10)
val nBi = BigInt(n)
var loop = true
while (loop) {
m = m + 1
if (L(m - 1)(mod(-ten.pow(m), nBi).intValue()) == 1) {
loop = false
} else {
L(m)(0) = 1
for (k <- 1 until n) {
L(m)(k) = math.max(L(m - 1)(k), L(m - 1)(mod(BigInt(k) - ten.pow(m), nBi).toInt))
}
}
}
var r = ten.pow(m)
var k = mod(-r, nBi)
for (j <- m - 1 to 1 by -1) {
if (L(j - 1)(k.toInt) == 0) {
r = r + ten.pow(j)
k = mod(k - ten.pow(j), nBi)
}
}
if (k == 1) {
r = r + 1
}
r
}
def mod(m: BigInt, n: BigInt): BigInt = {
var result = m % n
if (result < 0) {
result = result + n
}
result
}
}</lang>
- Output:
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) = 111111111111111111 = 99 * 1122334455667789 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) = 1111011111111111111 = 297 * 3740778151889263 A004290(576) = 111111111000000 = 576 * 192901234375 A004290(594) = 11110111111111111110 = 594 * 18703890759446315 A004290(891) = 1111111111111111011 = 891 * 1247038284075321 A004290(909) = 1011111111111111111 = 909 * 1112333455567779 A004290(999) = 111111111111111111111111111 = 999 * 111222333444555666777889 A004290(1998) = 1111111111111111111111111110 = 1998 * 556111667222778333889445 A004290(2079) = 1001101101111111111111 = 2079 * 481530111164555609 A004290(2251) = 101101101111 = 2251 * 44913861 A004290(2277) = 11110111111111111011 = 2277 * 4879275850290343 A004290(2439) = 10000101011110111101111111 = 2439 * 4100082415379299344449 A004290(2997) = 1111110111111111111111111111 = 2997 * 370740777814851888925963 A004290(4878) = 100001010111101111011111110 = 4878 * 20500412076896496722245
Sidef
Based on the Sage code by Eric M. Schmidt, which in turn is based on C code by Rick Heylen. <lang ruby>func find_B10(n, b=10) {
return 0 if (n == 0)
var P = n.of(-1)
for (var m = 0; P[0] == -1; ++m) {
for r in (0..n) {
next if (P[r] == -1)
next if (P[r] == m)
with ((powmod(b, m, n) + r) % n) { |t|
P[t] = m if (P[t] == -1)
}
}
}
var R = 0 var r = 0
do {
R += b**P[r]
r = (r - powmod(b, P[r], n))%n
} while (r > 0)
return R
}
printf("%5s: %28s %s\n", 'Number', 'B10', 'Multiplier')
for n in (1..10, 95..105, 297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878) {
printf("%6d: %28s %s\n", n, var a = find_B10(n), a/n)
}</lang>
- Output:
Number: B10 Multiplier
1: 1 1
2: 10 5
3: 111 37
4: 100 25
5: 10 2
6: 1110 185
7: 1001 143
8: 1000 125
9: 111111111 12345679
10: 10 1
95: 110010 1158
96: 11100000 115625
97: 11100001 114433
98: 11000010 112245
99: 111111111111111111 1122334455667789
100: 100 1
101: 101 1
102: 1000110 9805
103: 11100001 107767
104: 1001000 9625
105: 101010 962
297: 1111011111111111111 3740778151889263
576: 111111111000000 192901234375
594: 11110111111111111110 18703890759446315
891: 1111111111111111011 1247038284075321
909: 1011111111111111111 1112333455567779
999: 111111111111111111111111111 111222333444555666777889
1998: 1111111111111111111111111110 556111667222778333889445
2079: 1001101101111111111111 481530111164555609
2251: 101101101111 44913861
2277: 11110111111111111011 4879275850290343
2439: 10000101011110111101111111 4100082415379299344449
2997: 1111110111111111111111111111 370740777814851888925963
4878: 100001010111101111011111110 20500412076896496722245
Tcl
I have written this code from scratch in order to understand what is going on. Finally my code is quite similar to some other entries. <lang Tcl> package require Tcl 8.5
- power of ten, modulo --> (10**expo % modval) suited for large expo
proc potmod {expo modval} {
if {$expo < 0} { return 0 }
if {$modval < 2} { return 0 } ;# x mod 1 = 0
set r 1
set p [expr {10 % $modval}]
while {$expo} {
set half [expr {$expo / 2}]
set odd [expr {$expo % 2}]
if {$expo % 2} {
set r [expr {($r * $p) % $modval}] ;# r *= p
if {$r == 0} break
}
set expo [expr {$expo / 2}]
if {$expo} {
set p [expr {($p * $p) % $modval}] ;# p *= p
if {$p == 1} break
}
}
return $r
}
proc sho_sol {n r} {
puts "B10([format %4s $n]) = [format %28s $r] = n * [expr {$r / $n}]"
}
proc do_1 {n} {
if {$n < 2} {
sho_sol $n 1
return
}
set k 0 ;# running exponent for powers of 10
set potmn 1 ;# (k-th) power of ten mod n
set mvbyk($potmn) $k ;# highest k for sum with mod value
set canmv [list $potmn] ;# which indices are in mvbyk(.)
set solK -1 ;# highest exponent of first solution
for {incr k} {$k <= $n} {incr k} {
## By now we know what can be achieved below 10**k.
## Combine that with the new 10**k ...
set potmn [expr {(10 * $potmn) % $n}] ;# new power of 10
if {$potmn == 0} { ;# found a solution
set solK $k ; break
}
foreach mv $canmv {
## the mod value $mv can be constructed below $k
set newmv [expr {($potmn + $mv) % $n}]
## ... and now we can also do $newmv. Solution?
if {$newmv == 0} {
set solK $k ; break
}
if { ! [info exists mvbyk($newmv)] } { ;# is new
set mvbyk($newmv) $k ;# remember highest expo
lappend canmv $newmv
}
}
if {$solK >= 0} { break }
set newmv $potmn
if { ! [info exists mvbyk($newmv)] } {
set mvbyk($newmv) $k
lappend canmv $newmv
}
}
## Reconstruct solution ...
set k $solK
set mv 0 ;# mod value of $k and below (it is the solution)
set r "1" ;# top result, including $k
while 1 {
## 10**k is the current largest power of ten in the solution
## $r includes it, already, but $mv is not yet updated
set mv [expr {($mv - [potmod $k $n]) % $n}]
if {$mv == 0} {
append r [string repeat "0" $k]
break
}
set subk $mvbyk($mv)
append r [string repeat "0" [expr {$k - $subk - 1}]] "1"
set k $subk
}
sho_sol $n $r
}
proc do_range {lo hi} {
for {set n $lo} {$n <= $hi} {incr n} {
do_1 $n
}
}
do_range 1 10 do_range 95 105 foreach n {297 576 594 891 909 999 1998 2079 2251 2277 2439 2997 4878} {
do_1 $n
} </lang>
- Output:
B10( 1) = 1 = n * 1 B10( 2) = 10 = n * 5 B10( 3) = 111 = n * 37 B10( 4) = 100 = n * 25 B10( 5) = 10 = n * 2 B10( 6) = 1110 = n * 185 B10( 7) = 1001 = n * 143 B10( 8) = 1000 = n * 125 B10( 9) = 111111111 = n * 12345679 B10( 10) = 10 = n * 1 B10( 95) = 110010 = n * 1158 B10( 96) = 11100000 = n * 115625 B10( 97) = 11100001 = n * 114433 B10( 98) = 11000010 = n * 112245 B10( 99) = 111111111111111111 = n * 1122334455667789 B10( 100) = 100 = n * 1 B10( 101) = 101 = n * 1 B10( 102) = 1000110 = n * 9805 B10( 103) = 11100001 = n * 107767 B10( 104) = 1001000 = n * 9625 B10( 105) = 101010 = n * 962 B10( 297) = 1111011111111111111 = n * 3740778151889263 B10( 576) = 111111111000000 = n * 192901234375 B10( 594) = 11110111111111111110 = n * 18703890759446315 B10( 891) = 1111111111111111011 = n * 1247038284075321 B10( 909) = 1011111111111111111 = n * 1112333455567779 B10( 999) = 111111111111111111111111111 = n * 111222333444555666777889 B10(1998) = 1111111111111111111111111110 = n * 556111667222778333889445 B10(2079) = 1001101101111111111111 = n * 481530111164555609 B10(2251) = 101101101111 = n * 44913861 B10(2277) = 11110111111111111011 = n * 4879275850290343 B10(2439) = 10000101011110111101111111 = n * 4100082415379299344449 B10(2997) = 1111110111111111111111111111 = n * 370740777814851888925963 B10(4878) = 100001010111101111011111110 = n * 20500412076896496722245
Time: ~ 0.060 sec
Visual Basic .NET
<lang vbnet>Imports System, System.Linq, System.Collections.Generic, System.Console
Module Module1
Dim fmt As String = "{0,4} * {1,31:n0} = {2,-28}" & vbLf
Sub B10(ByVal n As Integer)
If n <= 1 Then Return
Dim pow As Integer() = New Integer(n) {},
val As Integer() = New Integer(n) {},
count As Integer = 0, ten As Integer = 1, x As Integer = 1
While x <= n : val(x) = ten : For j As Integer = 0 To n
If pow(j) <> 0 AndAlso pow((j + ten) Mod n) = 0 AndAlso _
pow(j) <> x Then pow((j + ten) Mod n) = x
Next : If pow(ten) = 0 Then pow(ten) = x
ten = (10 * ten) Mod n : If pow(0) <> 0 Then
x = n : Dim s As String = "" : While x <> 0
Dim p As Integer = pow(x Mod n)
If count > p Then s += New String("0"c, count - p)
count = p - 1 : s += "1"
x = (n + x - val(p)) Mod n : End While
If count > 0 Then s += New String("0"c, count)
Write(fmt, n, Decimal.Parse(s) / n, s) : Return
End If : x += 1 : End While : Write("Can't do it!")
End Sub
Sub Main(ByVal args As String())
Dim st As DateTime = DateTime.Now
Dim m As List(Of Integer) = New List(Of Integer) From _
{297,576,594,891,909,999,1998,2079,2251,2277,2439,2997,4878}
Write(fmt, "n", "multiplier", "B10")
WriteLine(New String("-"c, 69)) : Write(fmt, 1, 1, 1)
For n As Integer = 1 To m.Last()
If n <= 10 OrElse n >= 95 AndAlso n <= 105 OrElse m.Contains(n) Then B10(n)
Next : WriteLine(vbLf & "Took {0}ms", (DateTime.Now - st).TotalMilliseconds)
End Sub
End Module</lang>
- Output:
n * multiplier = B10 --------------------------------------------------------------------- 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 * 12,345,679 = 111111111 10 * 1 = 10 95 * 1,158 = 110010 96 * 115,625 = 11100000 97 * 114,433 = 11100001 98 * 112,245 = 11000010 99 * 1,122,334,455,667,789 = 111111111111111111 100 * 1 = 100 101 * 1 = 101 102 * 9,805 = 1000110 103 * 107,767 = 11100001 104 * 9,625 = 1001000 105 * 962 = 101010 297 * 3,740,778,151,889,263 = 1111011111111111111 576 * 192,901,234,375 = 111111111000000 594 * 18,703,890,759,446,315 = 11110111111111111110 891 * 1,247,038,284,075,321 = 1111111111111111011 909 * 1,112,333,455,567,779 = 1011111111111111111 999 * 111,222,333,444,555,666,777,889 = 111111111111111111111111111 1998 * 556,111,667,222,778,333,889,445 = 1111111111111111111111111110 2079 * 481,530,111,164,555,609 = 1001101101111111111111 2251 * 44,913,861 = 101101101111 2277 * 4,879,275,850,290,343 = 11110111111111111011 2439 * 4,100,082,415,379,299,344,449 = 10000101011110111101111111 2997 * 370,740,777,814,851,888,925,963 = 1111110111111111111111111111 4878 * 20,500,412,076,896,496,722,245 = 100001010111101111011111110 Took 21.863ms
Wren
Very fast. Taking less than 40ms even in Wren. <lang ecmascript>import "/fmt" for Fmt import "/big" for BigInt
var b10 = Fn.new { |n|
if (n == 1) {
Fmt.print("$4d: $28s $-24d", 1, "1", 1)
return
}
var n1 = n + 1
var pow = List.filled(n1, 0)
var val = List.filled(n1, 0)
var count = 0
var ten = 1
var x = 1
while (x < n1) {
val[x] = ten
for (j in 0...n1) {
if (pow[j] != 0 && pow[(j+ten)%n] == 0 && pow[j] != x) pow[(j+ten)%n] = x
}
if (pow[ten] == 0) pow[ten] = x
ten = (10*ten) % n
if (pow[0] != 0) break
x = x + 1
}
x = n
if (pow[0] != 0) {
var s = ""
while (x != 0) {
var p = pow[x%n]
if (count > p) s = s + ("0" * (count-p))
count = p - 1
s = s + "1"
x = (n + x - val[p]) % n
}
if (count > 0) s = s + ("0" * count)
var mpm = BigInt.new(s)
var mul = mpm/n
Fmt.print("$4d: $28s $-24i", n, s, mul)
} else {
System.print("Can't do it!")
}
}
var start = System.clock var tests = [
[1, 10], [95, 105], [297], [576], [594], [891], [909], [999], [1998], [2079], [2251], [2277], [2439], [2997], [4878]
] System.print(" n B10 multiplier") System.print("----------------------------------------------") for (test in tests) {
var from = test[0] var to = from if (test.count == 2) to = test[1] for (n in from..to) b10.call(n)
} System.print("\nTook %(System.clock-start) seconds.")</lang>
- Output:
n B10 multiplier ---------------------------------------------- 1: 1 1 2: 10 5 3: 111 37 4: 100 25 5: 10 2 6: 1110 185 7: 1001 143 8: 1000 125 9: 111111111 12345679 10: 10 1 95: 110010 1158 96: 11100000 115625 97: 11100001 114433 98: 11000010 112245 99: 111111111111111111 1122334455667789 100: 100 1 101: 101 1 102: 1000110 9805 103: 11100001 107767 104: 1001000 9625 105: 101010 962 297: 1111011111111111111 3740778151889263 576: 111111111000000 192901234375 594: 11110111111111111110 18703890759446315 891: 1111111111111111011 1247038284075321 909: 1011111111111111111 1112333455567779 999: 111111111111111111111111111 111222333444555666777889 1998: 1111111111111111111111111110 556111667222778333889445 2079: 1001101101111111111111 481530111164555609 2251: 101101101111 44913861 2277: 11110111111111111011 4879275850290343 2439: 10000101011110111101111111 4100082415379299344449 2997: 1111110111111111111111111111 370740777814851888925963 4878: 100001010111101111011111110 20500412076896496722245 Took 0.037077 seconds.
zkl
<lang zkl>var [const]
B10_4=10*10*10*10,
HexB10=T(0000,0001,0010,0011,0100,0101,0110,0111,
1000,1001,1010,1011,1100,1101,1110,1111);
// Convert n from binary as if it is Base 10
// limited for Uint64 to 2^20-1= 1048575 ala 19 digits
// for int64, limited to 2^19-1= 524287, conv2B10()-->1111111111111111111
const B10_MAX=(2).pow(19) - 1;
fcn conv2B10(n){
facB10,result := 1,0;
while(n>0){
result=facB10*HexB10[n.bitAnd(15)] + result;
n=n/16;
facB10*=B10_4;
}
result
} fcn findB10(n){ // --> -1 if overflow signed 64 bit int
i:=0;
while(i<B10_MAX){ if(conv2B10( i+=1 )%n == 0) return(conv2B10(i)); }
return(-1); // overflow 64 bit signed int
}</lang> <lang zkl>foreach r in (T([1..10],[95..105],
T(297, 576, 891, 909, 1998, 2079, 2251, 2277, 2439, 2997, 4878))){
foreach n in (r){
b10:=findB10(n);
if(b10==-1) println("B10(%4d): Out of range".fmt(n));
else println("B10(%4d) = %d = %d * %d".fmt(n,b10,n,b10/n));
}
}</lang>
- Output:
B10( 1) = 1 = 1 * 1 B10( 2) = 10 = 2 * 5 B10( 3) = 111 = 3 * 37 B10( 4) = 100 = 4 * 25 B10( 5) = 10 = 5 * 2 B10( 6) = 1110 = 6 * 185 B10( 7) = 1001 = 7 * 143 B10( 8) = 1000 = 8 * 125 B10( 9) = 111111111 = 9 * 12345679 B10( 10) = 10 = 10 * 1 B10( 95) = 110010 = 95 * 1158 B10( 96) = 11100000 = 96 * 115625 B10( 97) = 11100001 = 97 * 114433 B10( 98) = 11000010 = 98 * 112245 B10( 99) = 111111111111111111 = 99 * 1122334455667789 B10( 100) = 100 = 100 * 1 B10( 101) = 101 = 101 * 1 B10( 102) = 1000110 = 102 * 9805 B10( 103) = 11100001 = 103 * 107767 B10( 104) = 1001000 = 104 * 9625 B10( 105) = 101010 = 105 * 962 B10( 297) = 1111011111111111111 = 297 * 3740778151889263 B10( 576) = 111111111000000 = 576 * 192901234375 B10( 891) = 1111111111111111011 = 891 * 1247038284075321 B10( 909) = 1011111111111111111 = 909 * 1112333455567779 B10(1998): Out of range B10(2079): Out of range B10(2251) = 101101101111 = 2251 * 44913861 B10(2277): Out of range B10(2439): Out of range B10(2997): Out of range B10(4878): Out of range