I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Minimum positive multiple in base 10 using only 0 and 1

From Rosetta Code
Task
Minimum positive multiple in base 10 using only 0 and 1
You are encouraged to solve this task according to the task description, using any language you may know.

Every positive integer has infinitely many 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 this property.

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[edit]

Based on a translation of Rick Heylen's C in the 'Binary' Puzzle link on the OIES site.

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
 
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

AppleScript[edit]

Translation of: Phix

… reworked to be more understandable to myself. It returns the required results in 0.476 seconds on my machine, beating my own abandoned effort's 42 minutes and 16 seconds by some margin! I've used my own script's long-division code to get the multiplier and have incorporated the optimisation used at the top of the handler.

on b10(n)
if (n < 1) then error
-- Each factor of n that's either 10, 2, or 5 will contribute just a zero each to the end of the B10.
-- Count and lose any such factors here to leave a potentially much smaller n (nx) to process.
-- The relevant number of zeros will be appended to the shorter result afterwards.
set nx to n
set endZeroCount to 0
repeat with factor in {10, 5, 2}
repeat while (nx mod factor = 0)
set endZeroCount to endZeroCount + 1
set nx to nx div factor
end repeat
end repeat
 
script o
-- 'val' and 'pow' are uninformative and misleading labels for these lists, but I've
-- kept them for code comparison purposes and because I can't think of anything better.
property val : {} -- Will be successive powers of 10, mod nx.
property pow : {} -- Initially nx placeholders, some or all of which will be replaced with indices to slots in val.
property digits : {} -- Digits for output.
end script
 
if (nx = 1) then
set end of o's digits to 1 -- Clever stuff not needed.
else
set placeholder to missing value
repeat nx times
set end of o's pow to placeholder
end repeat
 
-- Calculate successive powers of 10, mod nx, (hereafter "powers"), storing them in val and
-- finding all the sums-mod-nx ("sums") that can be made from them and sums already obtained.
-- The range of possible sums (0 to nx - 1) is represented by positions in pow (index = sum + 1
-- with AppleScript's 1-based indices). Assign the index in val of the first power to produce
-- each sum to pow's slot for that sum. Stop when the index of the current power turns up in
-- pow's first slot, indicating that a subset of the powers obtained sums to nx (sum mod nx = 0)
-- and thus that the sum of the corresponding /un/modded powers of 10 is a multiple of nx.
 
-- The first power of 10 is always 1, its index in val is always 1, and its only possible sum is itself.
set p10 to 1 -- 10 ^ 0 mod nx.
set end of o's val to p10
set valIndex to 1
set item (p10 + 1) of o's pow to valIndex
-- Subsequent settings depend on the value of nx.
repeat until (beginning of o's pow = valIndex)
-- Get the next power of 10, mod nx.
set p10 to p10 * 10 mod nx
set end of o's val to p10
set valIndex to valIndex + 1
-- "Add" it to any existing sums by inserting its val index into the pow slot p10 places after (mod nx)
-- each slot already set for a lower-order p10, provided the target slot itself isn't already set.
repeat with powIndex from 1 to nx
set this to item powIndex of o's pow
if (this is placeholder) then
else if (this < valIndex) then
set targetIndex to (powIndex + p10 - 1) mod nx + 1
if (item targetIndex of o's pow is placeholder) then set item targetIndex of o's pow to valIndex
end if
end repeat
-- Ensure that it's also treated as a sum in its own right.
set targetIndex to p10 + 1
if (item targetIndex of o's pow is placeholder) then set item targetIndex of o's pow to valIndex
end repeat
 
-- To identify the powers-mod-nx which summed to nx, use pow unnecessarily to look up the index
-- of the power still in p10 which allowed the sum, subtract that power from the sum, use pow again
-- to find the lower-order power that allowed what's left, and so on until the sum's reduced to 0.
-- Append a 1 to the digit list for each power identified and a 0 each for any intervening ones.
set sum to nx
set previousIndex to 0
repeat until (sum = 0)
set valIndex to (item (sum mod nx + 1) of o's pow)
repeat (previousIndex - valIndex - 1) times
set end of o's digits to 0
end repeat
set end of o's digits to 1
set previousIndex to valIndex
set sum to (sum - (item valIndex of o's val) + nx) mod nx
end repeat
end if
 
-- Append any trailing zeros due from factors removed at the beginning.
repeat endZeroCount times
set end of o's digits to 0
end repeat
 
-- Coerce the list of 1s and 0s to text.
set bTen to join(o's digits, "")
-- Replace the list's contents with the results of dividing by the original n.
set digitCount to (count o's digits)
set remainder to 0
repeat with i from 1 to digitCount
set dividend to remainder * 10 + (item i of o's digits)
set item i of o's digits to dividend div n
set remainder to dividend mod n
end repeat
-- Zap any leading zeros in the result and coerce what's left to text.
repeat with i from 1 to digitCount
if (item i of o's digits > 0) then exit repeat
set item i of o's digits to ""
end repeat
set multiplier to join(o's digits, "")
 
return {n:n, b10:bTen, multiplier:multiplier}
end b10
 
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
 
local output, n, bTen, multiplier
set output to {}
repeat with n in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, ¬
297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878}
set {b10:bTen, multiplier:multiplier} to b10(n's contents)
set end of output to (n as text) & " * " & multiplier & (" = " & bTen)
end repeat
return join(output, linefeed)
Output:
 
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[edit]

Compiled using gcc for the 128 bit integer type

#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;
}
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#[edit]

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.

using System;
using System.Collections.Generic;
using static System.Console;
 
class Program {
 
static string B10(int n) {
int[] pow = new int[n + 1], val = new int[29];
for (int count = 0, ten = 1, x = 1; x <= n; x++) {
val[x] = ten;
for (int j = 0, t; j <= n; j++)
if (pow[j] != 0 && pow[j] != x && pow[t = (j + ten) % n] == 0)
pow[t] = 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);
return s;
}
}
return "1";
}
 
static void Main(string[] args) {
string fmt = "{0,4} * {1,24} = {2,-28}\n";
int[] m = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105,
297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878 };
string[] r = new string[m.Length];
WriteLine(fmt + new string('-', 62), "n", "multiplier", "B10");
var sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < m.Length; i++) r[i] = B10(m[i]);
sw.Stop();
for (int i = 0; i < m.Length; i++) Write(fmt, m[i], decimal.Parse(r[i]) / m[i], r[i]);
Write("\nTook {0}ms", sw.Elapsed.TotalMilliseconds);
}
}
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 1.9585ms
Timing from tio.run

C++[edit]

Translation of: C
#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;
}
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[edit]

Translation of: Java
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) - (ten ^^ 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 += ten ^^ 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;
}
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

F#[edit]

 
// 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)
 
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[edit]

This is just the naive implementation, converting the number to a string and checking every character.

: 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 ;

Go[edit]


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.

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))
}
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[edit]

A direct encoding, without any special optimizations, of the approach described in the Math.StackExchange article referenced in the task description.

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 <>)
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[edit]

Implementation of algorithm from the OIES site.

 
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);
}
}
 
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

jq[edit]

Translation of: Wren

Works with gojq, the Go implementation of jq

The C implementation of jq does not have sufficiently accurate integer arithmetic to get beyond n = 98, so only the results for a run of gojq are shown.

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
 
def pp(a;b;c): "\(a|lpad(4)): \(b|lpad(28)) \(c|lpad(24))";
 
def b10:
. as $n
| if . == 1 then pp(1;1;1)
else ($n + 1) as $n1
| { pow: [range(0;$n)|0],
val: [range(0;$n)|0],
count: 0,
ten: 1,
x: 1 }
| until (.x >= $n1;
.val[.x] = .ten
| reduce range(0;$n1) as $j (.;
if .pow[$j] != 0 and .pow[($j+.ten)%$n] == 0 and .pow[$j] != .x
then .pow[($j+.ten)%$n] = .x
else . end )
| if .pow[.ten] == 0 then .pow[.ten] = .x else . end
| .ten = (10*.ten) % $n
| if .pow[0] != 0 then .x = $n1 # .x will soon be reset
else .x += 1
end )
| .x = $n
| if .pow[0] != 0
then .s = ""
| until (.x == 0;
.pow[.x % $n] as $p
| if .count > $p then .s += ("0" * (.count-$p)) else . end
| .count = $p - 1
| .s += "1"
| .x = ( ($n + .x - .val[$p]) % $n ) )
| if .count > 0 then .s += ("0" * .count) else . end
| pp($n; .s; .s|tonumber/$n)
else "Can't do it!"
end
end;
 
def tests: [
[1, 10], [95, 105], [297], [576], [594], [891], [909], [999],
[1998], [2079], [2251], [2277], [2439], [2997], [4878]
];
 
pp("n"; "B10"; "multiplier"),
(pp("-";"-";"-") | gsub(".";"-")),
( tests[]
| .[0] as $from
| (if length == 2 then .[1] else $from end) as $to
| range($from; $to + 1)
| b10 )
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

Julia[edit]

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.

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
 
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[edit]

Translation of: Phix
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
 
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[edit]

Translation of: Java
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
}
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

Lua[edit]

Without a bignum library, some values do not display or calculate properly

Translation of: Ruby
function array1D(n, v)
local tbl = {}
for i=1,n do
table.insert(tbl, v)
end
return tbl
end
 
function array2D(h, w, v)
local tbl = {}
for i=1,h do
table.insert(tbl, array1D(w, v))
end
return tbl
end
 
function mod(m, n)
m = math.floor(m)
local result = m % n
if result < 0 then
result = result + n
end
return result
end
 
function getA004290(n)
if n == 1 then
return 1
end
local arr = array2D(n, n, 0)
arr[1][1] = 1
arr[1][2] = 1
local m = 0
while true do
m = m + 1
if arr[m][mod(-10 ^ m, n) + 1] == 1 then
break
end
arr[m + 1][1] = 1
for k = 1, n - 1 do
arr[m + 1][k + 1] = math.max(arr[m][k + 1], arr[m][mod(k - 10 ^ m, n) + 1])
end
end
local r = 10 ^ m
local k = mod(-r, n)
for j = m - 1, 1, -1 do
if arr[j][k + 1] == 0 then
r = r + 10 ^ j
k = mod(k - 10 ^ j, n)
end
end
if k == 1 then
r = r + 1
end
return r
end
 
function test(cases)
for _,n in ipairs(cases) do
local result = getA004290(n)
print(string.format("A004290(%d) = %s = %d * %d", n, math.floor(result), n, math.floor(result / n)))
end
end
 
test({1, 2, 3, 4, 5, 6, 7, 8, 9})
test({95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105})
test({297, 576, 594, 891, 909, 999})
--test({1998, 2079, 2251, 2277})
--test({2439, 2997, 4878})
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(95) = 110010 = 95 * 1158     
A004290(96) = 11100000 = 96 * 115625 
A004290(97) = 11100001 = 97 * 114433 
A004290(98) = 11000010 = 98 * 112245
A004290(99) = 111011111111111120 = 99 * 1121324354657688                <-- error
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) = 111011111111111120 = 297 * 373774784885896               <-- error
A004290(576) = 111111111000000 = 576 * 192901234375
A004290(594) = 1.0100010101011e+19 = 594 * 17003384008436194            <-- error
A004290(891) = 111111111111111024 = 891 * 124703828407532               <-- error
A004290(909) = 1011110111111111168 = 909 * 1112332355457768             <-- error
A004290(999) = 1.1000000001001e+19 = 999 * 11011011012013022            <-- error


Mathematica/Wolfram Language[edit]

ClearAll[B10]
B10[n_Integer] := Module[{i, out},
i = 1;
While[! Divisible[FromDigits[IntegerDigits[i, 2], 10], n],
i++;
];
out = FromDigits[IntegerDigits[i, 2], 10];
[email protected]{n, " x ", out/n, " = ", out}
]
Table[B10[i], {i, Range[10]}] // Column
Table[B10[i], {i, 95, 105}] // Column
B10[297]
B10[576]
B10[594]
B10[891]
B10[909]
B10[999]
B10[1998]
B10[2079]
B10[2251]
B10[2277]
B10[2439]
B10[2997]
B10[4878]
Output:
1 x 1 = 1
2 x 5 = 10
3 x 37 = 111
4 x 25 = 100
5 x 2 = 10
6 x 185 = 1110
7 x 143 = 1001
8 x 125 = 1000
9 x 12345679 = 111111111
10 x 1 = 10
95 x 1158 = 110010
96 x 115625 = 11100000
97 x 114433 = 11100001
98 x 112245 = 11000010
99 x 1122334455667789 = 111111111111111111
100 x 1 = 100
101 x 1 = 101
102 x 9805 = 1000110
103 x 107767 = 11100001
104 x 9625 = 1001000
105 x 962 = 101010
297 x 3740778151889263 = 1111011111111111111
576 x 192901234375 = 111111111000000
594 x 18703890759446315 = 11110111111111111110
891 x 1247038284075321 = 1111111111111111011
909 x 1112333455567779 = 1011111111111111111
999 x 111222333444555666777889 = 111111111111111111111111111
1998 x 556111667222778333889445 = 1111111111111111111111111110
2079 x 481530111164555609 = 1001101101111111111111
2251 x 44913861 = 101101101111
2277 x 4879275850290343 = 11110111111111111011
2439 x 4100082415379299344449 = 10000101011110111101111111
2997 x 370740777814851888925963 = 1111110111111111111111111111
4878 x 20500412076896496722245 = 100001010111101111011111110

Modula-2[edit]

Same approach as the math.stackexchange post referenced in the task description. This solution doesn't calculate the B10 itself; see the comment in the definition module.

 
DEFINITION MODULE B10AsBin;
 
(* Returns a number representing the B10 of the passed-in number N.
The result has the same binary digits as B10 has decimal digits,
e.g. N = 7 returns 9 = 1001 binary, representing 1001 decimal.
Returns 0 if the procedure fails.
In TopSpeed Modula-2, CARDINAL is unsigned 16-bit, LONGCARD is unsigned 32-bit.
*)

PROCEDURE CalcB10AsBinary( N : CARDINAL) : LONGCARD;
 
END B10AsBin.
 
 
IMPLEMENTATION MODULE B10AsBin;
 
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
 
PROCEDURE CalcB10AsBinary( N : CARDINAL) : LONGCARD;
CONST
MaxPower2 = 80000000H; (* 2^31 *)
VAR
pSums : POINTER TO ARRAY CARDINAL OF CARDINAL;
pWhen : POINTER TO ARRAY CARDINAL OF LONGCARD;
b10bin, pwr2 : LONGCARD;
j, j_stop, nrSums, res10, s : CARDINAL;
BEGIN
IF (N <= 1) THEN RETURN LONGCARD(N) END; (* dispose of trivial cases *)
(* TopSpeed Modula-2 doesn't seem to have dynamic arrays,
so we use a workaround *)

ALLOCATE( pSums, N*SIZE(CARDINAL));
ALLOCATE( pWhen, N*SIZE(LONGCARD));
FOR j := 0 TO N - 1 DO pWhen^[j] := 0; END;
 
b10bin := 0; (* result := 0; gets overwritten if procedure succeeds *)
res10 := 1; pwr2 := 1;
pSums^[0] := 0; pSums^[1] := 1; nrSums := 2;
pWhen^[1] := 1; (* record first occurrence of sum = 1 mod N *)
REPEAT
res10 := 10*res10 MOD N; pwr2 := 2*pwr2;
j := 0; j_stop := nrSums;
REPEAT
(* Possible new sums created by addition of res10 *)
s := pSums^[j] + res10;
IF (s >= N) THEN DEC(s, N); END; (* take sums mod N *)
IF (pWhen^[s] = 0) THEN (* if we haven't had this sum already *)
pWhen^[s] := pWhen^[pSums^[j]] + pwr2; (* record first occurrence *)
IF (s = 0) THEN b10bin := pWhen^[0]; (* if s = 0 then done *)
ELSE
pSums^[nrSums] := s; INC( nrSums); (* else store the sum s *)
END;
END;
INC(j);
UNTIL (j = j_stop) OR (b10bin > 0);
UNTIL (pwr2 = MaxPower2) OR (b10bin > 0);
DEALLOCATE( pSums, N*SIZE(CARDINAL));
DEALLOCATE( pWhen, N*SIZE(LONGCARD));
RETURN b10bin;
END CalcB10AsBinary;
END B10AsBin.
 
 
MODULE B10Demo;
 
FROM B10AsBin IMPORT CalcB10AsBinary;
IMPORT IO;
FROM Str IMPORT CardToStr;
 
CONST NrValues = 34;
TYPE DemoValues = ARRAY [1..NrValues] OF CARDINAL;
VAR
values : DemoValues;
b10 : LONGCARD;
j : CARDINAL;
b10Str : ARRAY [0..31] OF CHAR;
ok : BOOLEAN;
BEGIN
values := DemoValues( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105,
297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878);
FOR j := 1 TO NrValues DO
b10 := CalcB10AsBinary( values[j]);
CardToStr( b10, b10Str, 2, ok);
IO.WrCard( values[j], 4); IO.WrStr( ' ');
IO.WrStr( b10Str); IO.WrLn;
END;
END B10Demo.
 
Output:
   1  1
   2  10
   3  111
   4  100
   5  10
   6  1110
   7  1001
   8  1000
   9  111111111
  10  10
  95  110010
  96  11100000
  97  11100001
  98  11000010
  99  111111111111111111
 100  100
 101  101
 102  1000110
 103  11100001
 104  1001000
 105  101010
 297  1111011111111111111
 576  111111111000000
 594  11110111111111111110
 891  1111111111111111011
 909  1011111111111111111
 999  111111111111111111111111111
1998  1111111111111111111111111110
2079  1001101101111111111111
2251  101101101111
2277  11110111111111111011
2439  10000101011110111101111111
2997  1111110111111111111111111111
4878  100001010111101111011111110


Nim[edit]

Translation of: Phix
Library: bignum

As in the Phix solution the big integer library is only used to check the result and compute the factor.

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"
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
Time: 0.005 s

Pascal[edit]

Works with: Free 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

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.
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[edit]

Brutish and short[edit]

Brute-force code does the task minimum, but slowly (and that even with a short-circuit to avoid calculations for 99, 999)

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;
}
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[edit]

Much faster, while also completing stretch goal.

Translation of: Sidef
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;
}
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[edit]

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.

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)
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"

Python[edit]

Translation of: Kotlin
def getA004290(n):
if n < 2:
return 1
arr = [[0 for _ in range(n)] for _ in range(n)]
arr[0][0] = 1
arr[0][1] = 1
m = 0
while True:
m += 1
if arr[m - 1][-10 ** m % n] == 1:
break
arr[m][0] = 1
for k in range(1, n):
arr[m][k] = max([arr[m - 1][k], arr[m - 1][k - 10 ** m % n]])
r = 10 ** m
k = -r % n
for j in range((m - 1), 0, -1):
if arr[j - 1][k] == 0:
r = r + 10 ** j
k = (k - 10 ** j) % n
if k == 1:
r += 1
return r
 
for n in [i for i in range(1, 11)] + \
[i for i in range(95, 106)] + \
[297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878]:
result = getA004290(n)
print(f"A004290({n}) = {result} = {n} * {result // n})")
 
Output:
Same as Kotlin.


Raku[edit]

(formerly Perl 6)

Works with: Rakudo version 2020.02

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.

say $_ , ': ', (1..*).map( *.base(2) ).first: * %% $_ for flat 1..10, 95..105; # etc.

Based on Ed Pegg jr.s C code from Mathpuzzlers.com. Similar to Phix and Go entries.

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 / $_;
}
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[edit]

/*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
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[edit]

 
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
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
 
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
done...

Ruby[edit]

Translation of: Kotlin
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
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[edit]

Translation of: Java
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
}
}
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[edit]

Based on the Sage code by Eric M. Schmidt, which in turn is based on C code by Rick Heylen.

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)
}
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[edit]

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.

 
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
}
 
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[edit]

Translation of: C#
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
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[edit]

Translation of: Go
Library: Wren-fmt
Library: Wren-big

Very fast. Taking less than 40ms even in Wren.

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.")
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[edit]

Translation of: Pascal
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
}
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));
}
}
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