Minimum positive multiple in base 10 using only 0 and 1: Difference between revisions

 

 

This is simple to do, but can be challenging to do efficiently.

:* [[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|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

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)

{{out}}

<pre>

Real: 00:00:00.454, CPU: 00:00:00.640, GC gen0: 107, gen1: 3, gen2: 1

</pre>

 

=={{header|Go}}==

 

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 (

}

fmt.Printf("\nTook %s\n", time.Since(start))

 

{{out}}

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)

 

b10 n = read (digitMatch rems sums) :: Integer

where

until

(\(_, _, _, mb) -> isJust mb)

let m = rem (10 ^ e) n

(0, [], [], Nothing)

 

digitMatch [] _ = []

digitMatch xs [] = '0' <$ xs

 

main :: IO ()

mapM_

{{Out}}

<pre> 1 * 1 -> 1

909 * 1112333455567779 -> 1011111111111111111

999 * 111222333444555666777889 -> 111111111111111111111111111</pre>

 

=={{header|Java}}==

Implementation of algorithm from the OIES site.

import java.math.BigInteger;

import java.util.ArrayList;

}

}

{{Out}}

<pre>

A004290(2997) = 1111110111111111111111111111 = 2997 * 370740777814851888925963

A004290(4878) = 100001010111101111011111110 = 4878 * 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)

println("B10($n) = $n * $(div(i, n)) = $i")

end

<pre>

B10(1) = 1 * 1 = 1

=== Puzzle algorithm version ===

{{trans|Phix}}

n == 1 && return one(Int128)

num, count, ten = n + 1, 0, 1

println("B10($n) = $n * $(div(i, n)) = $i")

end

<pre>

B10(1) = 1 * 1 = 1

0.054239 seconds (1.67 k allocations: 917.734 KiB)

</pre>

 

=={{header|Pascal}}==

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

check_B10(9999);

check_B10(2*9999); //real 0m0,077s :-)

{{out}}

<pre style="height:150px; overflow: auto;">

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

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

Much faster, while also completing stretch goal.

{{trans|Sidef}}

use warnings;

use Math::AnyNum qw(:overload powmod);

my $a = B10($n);

printf "%6d: %28s %s\n", $n, $a, $a/$n;

{{out}}

<pre style="height:30ex"> 1: 1 1

=={{header|Phix}}==

Using the Ed Pegg Jr 'Binary' Puzzle algorithm as linked to by OEIS.<br>

{{out}}

<pre>

"0.1s"

</pre>

 

=={{header|Raku}}==

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.

 

 

Based on [http://www.mathpuzzle.com/Binary.html Ed Pegg jr.s C code] from Mathpuzzlers.com. Similar to Phix and Go entries.

 

return 1 if n == 1;

my ($count, $power-mod-n) = 0, 1;

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

 

=={{header|REXX}}==

parse arg list

if list=='' then list= 1..10 95..105 297

say center(' N ', 9, "─") center(' B10 ', w, "─") center(' multiplier ', w, "─")

 

 

/*──────────────────────────────────────────────────────────────────────────────────────*/

commas: parse arg _; do c=length(_)-3 to 1 by -3; _= insert(',', _, c); end; return _

/*──────────────────────────────────────────────────────────────────────────────────────*/

select

end

when right(z, 1)==7 then do; start=3; inc= 10; end

otherwise nop

q= length(start)

if q>digits() then numeric digits q

end /*m*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

999 111,111,111,111,111,111,111,111,111 111,222,333,444,555,666,777,889

</pre>

 

=={{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)

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>

=={{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.

package require Tcl 8.5

 

do_1 $n

}

{{out}}

<pre>

</pre>

Time: ~ 0.060 sec

 

=={{header|zkl}}==

{{trans|Pascal}}

B10_4=10*10*10*10,

HexB10=T(0000,0001,0010,0011,0100,0101,0110,0111,

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

else println("B10(%4d) = %d = %d * %d".fmt(n,b10,n,b10/n));

}

{{out}}

<pre style="height:45ex">