Minimum positive multiple in base 10 using only 0 and 1: Difference between revisions
Minimum positive multiple in base 10 using only 0 and 1 (view source)
Revision as of 10:07, 4 January 2024
, 4 months ago→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (Change to task status) |
m (→{{header|Wren}}: Minor tidy) |
||
(23 intermediate revisions by 12 users not shown) | |||
Line 1:
{{task}}
Every positive integer has
This is simple to do, but can be challenging to do efficiently.
Line 41:
:* [[oeis:A004290|OEIS:A004290 Least positive multiple of n that when written in base 10 uses only 0's and 1's.]]
:* [https://math.stackexchange.com/questions/388165/how-to-find-the-smallest-number-with-just-0-and-1-which-is-divided-by-a-give How to find Minimum Positive Multiple in base 10 using only 0 and 1]
=={{header|11l}}==
{{trans|Kotlin}}
<syntaxhighlight lang="11l">F modp(m, n)
V result = m % n
I result < 0
result += n
R result
F getA004290(n)
I n == 1
R BigInt(1)
V arr = [[0] * n] * n
arr[0][0] = 1
arr[0][1] = 1
V m = 0
V ten = BigInt(10)
V nBi = BigInt(n)
L
m++
I arr[m - 1][Int(modp(-pow(ten, m), nBi))] == 1
L.break
arr[m][0] = 1
L(k) 1 .< n
arr[m][k] = max(arr[m - 1][k], arr[m - 1][Int(modp(BigInt(k) - pow(ten, m), nBi))])
V r = pow(ten, m)
V k = Int(modp(-r, nBi))
L(j) (m - 1 .< 0).step(-1)
I arr[j - 1][k] == 0
r += pow(ten, j)
k = Int(modp(BigInt(k) - pow(ten, j), nBi))
I k == 1
r++
R r
L(n) Array(1..10) [+] Array(95..105) [+] [297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878]
V result = getA004290(n)
print(‘A004290(’n‘) = ’result‘ = ’n‘ * ’(result I/ n))</syntaxhighlight>
{{out}}
<pre>
A004290(1) = 1 = 1 * 1
A004290(2) = 10 = 2 * 5
A004290(3) = 111 = 3 * 37
A004290(4) = 100 = 4 * 25
A004290(5) = 10 = 5 * 2
A004290(6) = 1110 = 6 * 185
A004290(7) = 1001 = 7 * 143
A004290(8) = 1000 = 8 * 125
A004290(9) = 111111111 = 9 * 12345679
A004290(10) = 10 = 10 * 1
A004290(95) = 110010 = 95 * 1158
A004290(96) = 11100000 = 96 * 115625
A004290(97) = 11100001 = 97 * 114433
A004290(98) = 11000010 = 98 * 112245
A004290(99) = 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
</pre>
=={{header|ALGOL 68}}==
Based on a translation of Rick Heylen's C in the 'Binary' Puzzle link on the OIES site.
<
# 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 #
Line 109 ⟶ 187:
FOR n FROM LWB tests TO UPB tests DO show b10( tests[ n ] ) OD
END
</syntaxhighlight>
{{out}}
<pre>
Line 147 ⟶ 225:
4878: 100001010111101111011111110 = 4878 * 20500412076896496722245
</pre>
=={{header|AppleScript}}==
{{trans|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.
<syntaxhighlight lang="applescript">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)</syntaxhighlight>
{{out}}
<syntaxhighlight lang="applescript">"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"</syntaxhighlight>
=={{header|C}}==
Compiled using gcc for the 128 bit integer type
<
#include <stdint.h>
#include <stdio.h>
Line 306 ⟶ 547:
return 0;
}</
{{out}}
<pre>1 * 1 = 1
Line 348 ⟶ 589:
Since C# has a ''decimal'' type, it can be used instead of an external 128 bit integer package to compute the multiplier.
<
using System.Collections.Generic;
using static System.Console;
class Program {
static string
int[] pow = new int[n + 1], val = new int[29];
ten = (10 * ten) %
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 "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 };
WriteLine(fmt + new string('-', 62), "n", "multiplier", "B10");
var sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; 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);
}
}</syntaxhighlight>
{{out}}
<pre> n * multiplier = B10
Line 419 ⟶ 673:
4878 * 20500412076896496722245 = 100001010111101111011111110
Took
</pre>Timing from tio.run
=={{header|C++}}==
{{trans|C}}
<
#include <vector>
Line 571 ⟶ 825:
return 0;
}</
{{out}}
<pre>1 * 1 = 1
Line 610 ⟶ 864:
=={{header|D}}==
{{trans|Java}}
<
import std.array;
import std.bigint;
Line 643 ⟶ 897:
L[m][0] = 1;
foreach (k; 1..n) {
L[m][k] = max(L[m - 1][k], L[m - 1][mod(BigInt(k) - (
}
}
Line 651 ⟶ 905:
assert(j != m);
if (L[j - 1][k.toInt] == 0) {
r +=
k = mod(k - (ten ^^ j), nBi);
}
Line 667 ⟶ 921:
}
return result;
}</
{{out}}
<pre>A004290(1) = 1 = 1 * 1
Line 683 ⟶ 937:
A004290(97) = 11100001 = 97 * 114433
A004290(98) = 11000010 = 98 * 112245
A004290(99) =
A004290(100) = 100 = 100 * 1
A004290(101) = 101 = 101 * 1
Line 690 ⟶ 944:
A004290(104) = 1001000 = 104 * 9625
A004290(105) = 101010 = 105 * 962
A004290(297) =
A004290(576) =
A004290(594) =
A004290(891) =
A004290(909) =
A004290(999) =
A004290(1998) =
A004290(2079) =
A004290(2251) = 101101101111 = 2251 * 44913861
A004290(2277) =
A004290(2439) =
A004290(2997) =
A004290(4878) =
</pre>
=={{header|F_Sharp|F#}}==
<
// 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
Line 717 ⟶ 972:
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)
</syntaxhighlight>
{{out}}
<pre>
Line 759 ⟶ 1,014:
=={{header|Factor}}==
This is just the naive implementation, converting the number to a string and checking every character.
<syntaxhighlight lang="factor">: is-1-or-0 ( char -- ? ) dup CHAR: 0 = [ drop t ] [ CHAR: 1 = ] if ;
: int-is-B10 ( n -- ? ) unparse [ is-1-or-0 ] all? ;
: B10-step ( x x -- x x ? ) dup int-is-B10 [ f ] [ over + t ] if ;
: find-B10 ( x -- x ) dup [ B10-step ] loop nip ;</syntaxhighlight>
=={{header|FreeBASIC}}==
{{trans|Ring}}
<syntaxhighlight lang="freebasic">#define limit1 900
#define limit2 18703890759446315
Dim As Ulongint nplus, lenplus, prod
Dim As Boolean plusflag = false, flag
Dim As String pstr
Dim As Integer plus(6) = {297,576,594,891,909,999}
Print !"Minimum positive multiple in base 10 using only 0 and 1:\n"
Print " N * multiplier = B10"
For n As Ulongint = 1 To limit1
If n = 106 Then
plusflag = true
nplus = 0
End If
lenplus = Ubound(plus)
If plusflag = true Then
nplus += 1
If nplus < lenplus+1 Then
n = plus(nplus)
Else
Exit For
End If
End If
For m As Ulongint = 1 To limit2
flag = true
prod = n*m
pstr = Str(prod)
For p As Ulongint = 1 To Len(pstr)
If Not(Mid(pstr,p,1) = "0" Or Mid(pstr,p,1) = "1") Then
flag = false
Exit For
End If
Next p
If flag = true Then
Print Using "### * ################ = &"; n; m; pstr
Exit For
End If
Next m
If n = 10 Then n = 94 : End If
Next n
Sleep</syntaxhighlight>
=={{header|Go}}==
Line 772 ⟶ 1,070:
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.
<
import (
Line 845 ⟶ 1,143:
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</
{{out}}
Line 893 ⟶ 1,191:
A direct encoding, without any special optimizations, of the approach described in the Math.StackExchange article referenced in the task description.
<
import Data.List (find)
import Data.Maybe (isJust)
Line 949 ⟶ 1,247:
justifyLeft, justifyRight :: Int -> a -> [a] -> [a]
justifyLeft n c s = take n (s <> replicate n c)
justifyRight n c = (drop . length) <*> (replicate n c <>)</
{{Out}}
<pre> 1 * 1 -> 1
Line 978 ⟶ 1,276:
909 * 1112333455567779 -> 1011111111111111111
999 * 111222333444555666777889 -> 111111111111111111111111111</pre>
=={{header|J}}==
Implementation derived from the maple algorithm at https://oeis.org/A004290:
<syntaxhighlight lang="j">B10=: {{ NB. https://oeis.org/A004290
next=. {{ {: (u -) 10x^# }}
step=. ([>. [ {~ y|(i.y)+]) next
continue=. 0 = ({~y|]) next
L=.1 0,~^:(y>1) (, step)^:continue^:_ ,:y{.1 1
k=. y|-r=.10x^<:#L
for_j. i.-<:#L do.
if. 0=L{~<k,~j-1 do.
k=. y|k-E=. 10x^j
r=. r+E
end.
end. r assert. 0=y|r
}}</syntaxhighlight>
Task example:
<syntaxhighlight lang="j">through=: {{ m+i.1+n-m }}
(,.B10"0) 1 through 10, 95 through 105, 297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878
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</syntaxhighlight>
=={{header|Java}}==
Implementation of algorithm from the OIES site.
<
import java.math.BigInteger;
import java.util.ArrayList;
Line 1,077 ⟶ 1,433:
}
}
</syntaxhighlight>
{{Out}}
<pre>
Line 1,114 ⟶ 1,470:
A004290(2997) = 1111110111111111111111111111 = 2997 * 370740777814851888925963
A004290(4878) = 100001010111101111011111110 = 4878 * 20500412076896496722245
</pre>
=={{header|jq}}==
{{trans|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.
<syntaxhighlight lang="jq">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 )</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Julia}}==
Uses the iterate in base 2, check for a multiple in base 10 method. Still slow but gets time below 1 minute by calculating the base 10 number within the same loop as the one that finds the base 2 digits.
<
for i in Int128(1):typemax(Int128)
q, b10, place = i, zero(Int128), one(Int128)
Line 1,138 ⟶ 1,592:
println("B10($n) = $n * $(div(i, n)) = $i")
end
</
<pre>
B10(1) = 1 * 1 = 1
Line 1,176 ⟶ 1,630:
=== Puzzle algorithm version ===
{{trans|Phix}}
<
n == 1 && return one(Int128)
num, count, ten = n + 1, 0, 1
Line 1,216 ⟶ 1,670:
println("B10($n) = $n * $(div(i, n)) = $i")
end
</
<pre>
B10(1) = 1 * 1 = 1
Line 1,258 ⟶ 1,712:
=={{header|Kotlin}}==
{{trans|Java}}
<
fun main() {
Line 1,325 ⟶ 1,779:
}
return result
}</
{{out}}
<pre>A004290(1) = 1 = 1 * 1
Line 1,365 ⟶ 1,819:
Without a bignum library, some values do not display or calculate properly
{{trans|Ruby}}
<
local tbl = {}
for i=1,n do
Line 1,433 ⟶ 1,887:
test({297, 576, 594, 891, 909, 999})
--test({1998, 2079, 2251, 2277})
--test({2439, 2997, 4878})</
{{out}}
<pre>A004290(1) = 1 = 1 * 1
Line 1,461 ⟶ 1,915:
A004290(909) = 1011110111111111168 = 909 * 1112332355457768 <-- error
A004290(999) = 1.1000000001001e+19 = 999 * 11011011012013022 <-- error</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">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];
Row@{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]</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Modula-2}}==
{{works with|TopSpeed (JPI) Modula-2 under DOSBox-X}}
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.
<syntaxhighlight lang="modula2">
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.
</syntaxhighlight>
<syntaxhighlight lang="modula2">
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.
</syntaxhighlight>
<syntaxhighlight lang="modula2">
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.
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
Line 1,468 ⟶ 2,113:
As in the Phix solution the big integer library is only used to check the result and compute the factor.
<
import bignum
Line 1,514 ⟶ 2,159:
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"</
{{out}}
Line 1,559 ⟶ 2,204:
gmp is only used, to get the multiplier.<BR>
Now lightning fast
<
//numbers having only digits 0 and 1 in their decimal representation
//see https://oeis.org/A004290
Line 1,711 ⟶ 2,356:
check_B10(9999);
check_B10(2*9999); //real 0m0,077s :-)
end.</
{{out}}
<pre style="height:150px; overflow: auto;">
Line 1,755 ⟶ 2,400:
===Brutish and short===
Brute-force code does the task minimum, but slowly (and that even with a short-circuit to avoid calculations for 99, 999)
<
use warnings;
use Math::AnyNum qw(:overload as_bin digits2num);
Line 1,764 ⟶ 2,409:
else { while (1) { last unless as_bin(++$y) % $x } }
printf "%4d: %28s %s\n", $x, as_bin($y), as_bin($y)/$x;
}</
{{out}}
<pre style="height:30ex"> 1: 1 1
Line 1,797 ⟶ 2,442:
Much faster, while also completing stretch goal.
{{trans|Sidef}}
<
use warnings;
use Math::AnyNum qw(:overload powmod);
Line 1,827 ⟶ 2,472:
my $a = B10($n);
printf "%6d: %28s %s\n", $n, $a, $a/$n;
}</
{{out}}
<pre style="height:30ex"> 1: 1 1
Line 1,866 ⟶ 2,511:
=={{header|Phix}}==
Using the Ed Pegg Jr 'Binary' Puzzle algorithm as linked to by OEIS.<br>
Very fast, finishes near-instantly, only needs/uses gmp to validate the results.<br>
You can run this online [http://phix.x10.mx/p2js/b10.htm here].
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">b10</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">"1"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">NUM</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ten</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">val</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">NUM</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">pow</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">NUM</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Calculate each 10^k mod n, along with all possible sums that can be
-- made from it and
--
-- ten/val[]
--
-- 10^1 = 10 mod 7 = 3. Possible sums: 1 3 4
--
--
--
-- ie since 10^3 mod 7 + 10^0 mod 7 == (6+1) mod 7 == 0, we know that
--
--
--
-- 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.
--</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">val</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ten</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">NUM</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">x</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (j seen, in a prior iteration)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ten</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span> <span style="color: #000080;font-style:italic;">-- (k was seen in this iteration)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ten</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ten</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ten</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">*</span><span style="color: #000000;">ten</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Can't do it!"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">--
-- 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.
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">x</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">></span><span style="color: #000000;">pm</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">-</span><span style="color: #000000;">pm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pm</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">;</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'1'</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">val</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pm</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">105</span><span style="color: #0000FF;">,</span><span style="color: #000000;">95</span><span style="color: #0000FF;">)&{</span><span style="color: #000000;">297</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">576</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">891</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">909</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">999</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1998</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2079</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2251</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2277</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2439</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2997</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4878</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">m10</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">r10</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b10</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">r10</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">" ??"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d * %-24s = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m10</span><span style="color: #0000FF;">),</span><span style="color: #000000;">r10</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,974 ⟶ 2,623:
"0.1s"
</pre>
=={{header|Python}}==
{{trans|Kotlin}}
<syntaxhighlight lang="python">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})")
</syntaxhighlight>{{out}} Same as Kotlin.
=={{header|Raku}}==
Line 1,980 ⟶ 2,663:
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.
<syntaxhighlight lang="raku"
Based on [http://www.mathpuzzle.com/Binary.html Ed Pegg jr.s C code] from Mathpuzzlers.com. Similar to Phix and Go entries.
<syntaxhighlight lang="raku"
return 1 if n == 1;
my ($count, $power-mod-n) = 0, 1;
Line 2,014 ⟶ 2,697:
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 / $_;
}</
{{out}}
<pre>Number: B10 Multiplier
Line 2,053 ⟶ 2,736:
=={{header|REXX}}==
<
numeric digits 30; w= length( commas( copies(1, digits()))) /*for formatting numbers.*/
parse arg list
Line 2,087 ⟶ 2,770:
do m=start by inc until verify(p, 10)==0; p= # * m
end /*m*/
return m</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,123 ⟶ 2,806:
=={{header|Ring}}==
<
see "working..." + nl
see "Minimum positive multiple in base 10 using only 0 and 1:" + nl
Line 2,167 ⟶ 2,850:
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 2,204 ⟶ 2,887:
=={{header|Ruby}}==
{{trans|Kotlin}}
<
result = m % n
if result < 0 then
Line 2,250 ⟶ 2,933:
result = getA004290(n)
print "A004290(%d) = %d = %d * %d\n" % [n, result, n, result / n]
end</
{{out}}
<pre>A004290(1) = 1 = 1 * 1
Line 2,289 ⟶ 2,972:
=={{header|Scala}}==
{{trans|Java}}
<
object MinimumNumberOnlyZeroAndOne {
Line 2,359 ⟶ 3,042:
result
}
}</
{{out}}
<pre>A004290(1) = 1 = 1 * 1
Line 2,398 ⟶ 3,081:
=={{header|Sidef}}==
Based on the [https://oeis.org/A004290/a004290_1.sage.txt Sage code by Eric M. Schmidt], which in turn is based on [http://www.mathpuzzle.com/Binary.html C code by Rick Heylen].
<
return 0 if (n == 0)
Line 2,431 ⟶ 3,114:
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)
}</
{{out}}
<pre>
Line 2,473 ⟶ 3,156:
=={{header|Tcl}}==
I have written this code from scratch in order to understand what is going on. Finally my code is quite similar to some other entries.
<syntaxhighlight lang="tcl">
package require Tcl 8.5
Line 2,570 ⟶ 3,253:
do_1 $n
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,612 ⟶ 3,295:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 2,648 ⟶ 3,331:
Next : WriteLine(vbLf & "Took {0}ms", (DateTime.Now - st).TotalMilliseconds)
End Sub
End Module</
{{out}}
<pre> n * multiplier = B10
Line 2,695 ⟶ 3,378:
{{libheader|Wren-big}}
Very fast. Taking less than 40ms even in Wren.
<
import "./big" for BigInt
var b10 = Fn.new { |n|
Line 2,751 ⟶ 3,434:
for (n in from..to) b10.call(n)
}
System.print("\nTook %(System.clock-start) seconds.")</
{{out}}
Line 2,797 ⟶ 3,480:
=={{header|zkl}}==
{{trans|Pascal}}
<
B10_4=10*10*10*10,
HexB10=T(0000,0001,0010,0011,0100,0101,0110,0111,
Line 2,820 ⟶ 3,503:
while(i<B10_MAX){ if(conv2B10( i+=1 )%n == 0) return(conv2B10(i)); }
return(-1); // overflow 64 bit signed int
}</
<
T(297, 576, 891, 909, 1998, 2079, 2251, 2277, 2439, 2997, 4878))){
foreach n in (r){
Line 2,828 ⟶ 3,511:
else println("B10(%4d) = %d = %d * %d".fmt(n,b10,n,b10/n));
}
}</
{{out}}
<pre style="height:45ex">
|