# Talk:Minimum positive multiple in base 10 using only 0 and 1

## Contents

## something's wrong[edit]

In the task's preamble (in the **E.G.** section), the 4^{th} multiplication (for a **B10** of **111,111,111**), the multiplier is incorrect. The multiplier shown would yield a **B10** value of **1,111,111,101**, which isn't the minimum **B10** for a **N** of **9**. -- Gerard Schildberger (talk) 18:57, 29 February 2020 (UTC)

- Hi Gerard, you multiply 'n' by the multiplier so 9 x 12,345,679 = 111,111,111 --PureFox (talk) 19:19, 29 February 2020 (UTC)

- That's all well and good. But, the example that I was talking about shows that
**9 × 123,456,789**which is the number shown in the task's preamble, not**9 × 12,345,679**. -- Gerard Schildberger (talk) 19:32, 29 February 2020 (UTC)

- That's all well and good. But, the example that I was talking about shows that

- But, "it" could've been an incorrect
**B10**, where the**B10**coulda/shoulda/woulda have been**1,111,111,101**, which would make the original multiplier correct. I could've corrected either value, but one does not want to be accused of vandalism (again). -- Gerard Schildberger (talk) 19:49, 29 February 2020 (UTC)

- But, "it" could've been an incorrect

- Ah. I did mess that up. Should know better than to transcribe stuff manually. Thanks to Gerard++ for calling attention to it and Purefox++ for fixing it. I was out most of yesterday afternoon / evening so didn't react quickly. --Thundergnat (talk) 20:17, 1 March 2020 (UTC)

## need for speed[edit]

in my Pascal version I use modular arithmetic.
First I create a list of all B10 upto 19 Digits, thats only Limit = 2^19= 524288 values.

While searching for Low Value aka LV =B10(i). LV MOD N == 0 I memorize (LV MOD N) and the position of the first occurence of (LV MOD N)

This list has the indices 0 to N-1, preset with -1, and the i of B10(i) is inserted at (LV MOD N)
When I found a value I am finished and go to output.

Else I start with a High Value HV =B10(j) | j =1..Limit.This HV is shifted by 10^19, but only modular

so (HV*10^19) MOD N <=> ((HV MOD N)*(10^19 MOD N) MOD N

(HV MOD N) is alredy calculated,(10^19 MOD N) once for N

To generate the new number (HV+LV ) MOD N I only have to add (HV mod N) + (LV mod N) the result = 0.. 2*n-2.

But only (HV mod N) + (LV mod N) = N is equal to ((HV mod N) + (LV mod N)) MOD N = 0, what is the search for.

Now I am only check if (N-(HV mod N)) is in the list of first occurence.

The values upto 9998 are the same as in OEIS:oeis.org/A004290/b004290.txt

There are only 98 values upto 1E6, which are out of range.But first I have to set ModToIdx : array[0..1000000] of Int32

--Horst.h 17:00, 1 March 2020 (UTC)~

## How does it work "C code for Ed Pegg Jr's 'Binary' Puzzle algorithm" ?[edit]

it is really fast, especially for numbers which result in a big number like 9999.
2000x checks of 9999 are done in 0,37 s vs my version with 10.7s.

But checking 1..100000 takes real 3m44,890s vs 1m18,507s

**But how does it work?**

//copyright http://www.mathpuzzle.com/Binary.html

//slightly modified (runtime 6m -> 3,75m )

#include <stdio.h>

#define NUM 100000

int main(int argc, char* argv[]){

signed long pow[NUM+1],val[NUM+1],x,num,ten;

int i,j,count,n1;

for(num=1;num<=NUM;num++){

n1 = num+1;

//clear pow

for(i=0;i<=n1;pow[i++]=0);

count=0;

for(ten=1,x=1;x<=n1;x++){

//ten == 10^(x-1)%num

val[x]=ten;

int mod = ten;

for(j=0;j<n1;j++){

if(pow[j]&&pow[j]!=x&&!pow[mod])

pow[mod]=x;}

mod++;

if(mod==num)

mod =0;

}

if(!pow[ten])

pow[ten]=x;

ten=(10*ten)%num;

if(pow[0])

break;

}

x=num;

printf("%ld\tdivides\t",x=num);

if(pow[0]){

int mod = 0;

while(x){

while(--count>pow[mod]-1)

printf("0");

count=pow[mod]-1;

printf("1");

x=(num+x-val[pow[mod]])%num;

mod = x;

}

while(count-->0)printf("0");

}

else {

printf("Can't do it!");

getchar();

}

printf("\n");

//getchar();

}

}

--Horst.h 14:10, 2 March 2020 (UTC)~

- No idea, however I had four (unrelated) minor insights: 1) B10(n) where n is all-nines is all-ones, in fact 9*length(n) ones. 2) No smallest multiplier ends with 0. 3) B10(2n) is either B10(n) [If n ends in 5, I think] or B10(n)*10, and the multiplier must end in 5. 4) for B10(k*10+n) where n is odd {1,3,5,7,9}, the multiplier must end in {1,7,(2/4/6/8),3,9}. Note that between them, rules 3 and 4 cover a trailing {1..9}, once each. None of those really help explain anything though. --Pete Lomax (talk) 15:36, 2 March 2020 (UTC)

- I've added a reference "How to find Minimum Positive Multiple in base 10 using only 0 and 1" which I think helps.--Nigel Galloway (talk) 13:49, 3 March 2020 (UTC)
- Thanks, that helps allot --Horst.h 14:09, 3 March 2020 (UTC)

- On that link, I see

10^{0}= 1 mod 7 possible sums: 1 10^{1}= 10 = 3 mod 7 possible sums: 1, 3, 4 10^{2}= 10*3 = 30 = 2 mod 7 possible sums: 1, 2, 3, 4, 5, 6

- but on the third line, I don't get the "10^2==10*3" part. What do I need to read to clue me in on that? --Pete Lomax (talk) 04:10, 5 March 2020 (UTC)
- The multiplication by 3 is not crucial to understanding the code. The important principal is that (n mod z) + (g mod z) = (n+g) mod z (see Casting_out_nines. So:

10^{0}= 1 mod 7 = 1 -> possible sums: 1 10^{1}= 10 mod 7 = 3 -> possible sums: 1, 3, 4 10^{2}= 100 mod 7 = 2 -> possible sums: 1, 2, 3, 4, 5, 6

I could rewrite this as: 10^{0}= 1 mod 7 = 1 -> possible sums: 1 10^{1}= 1^{1}0 = 10 mod 7 = 3 -> possible sums: 1, 3, 4 10^{2}= 1^{1}0^{3}0 = 30 mod 7 = 2 -> possible sums: 1, 2, 3, 4, 5, 6 where the additional superscripts are the carries as if I were back at school learning long division.

So the whole thing is: 1 -> 1 1^{1}0 -> 3 1^{1}1 -> 4 1^{1}0^{3}0 -> 2 1^{1}0^{3}1 -> 3 1^{1}1^{4}0 -> 5 1^{1}1^{4}1 -> 6 1^{1}0^{1}0^{2}0 -> 6 1^{1}0^{1}0^{2}1 -> 0 Success this is divisible by 7. Note that because (n mod 7) + (g mod 7) = (n+g) mod 7 I only need to calculate 100 mod 7 and I know say 110 mod 7 is (100 mod 7) + (10 mod 7) so I can calculate all possible sums by adding 100 mod 7 to the sums I already have in a modular way.

--Nigel Galloway (talk) 15:00, 14 March 2020 (UTC)

## general observations[edit]

If the **n** is only composed of ones and zeros, then the **B10** is equal to **n**.

If the **n** is only composed of nines, then the **B10** is composed of the shown digits below:

- For
**9**, the**B10**digits are**12345678**, and change the last eight to a nine. - For
**99**, the**B10**digits are**1122334455667788**, and change the last eight to a nine. - For
**999**, the**B10**digits are**111222333444555666777888**, and change the last eight to a nine. - For
**9999**, the**B10**digits are**11112222333344445555666677778888**, and change the last eight to a nine.

- For

I'm sure there is a more elegant way of expressing this, but I think showing is better than telling (the pattern seems obvious enough). -- Gerard Schildberger (talk) 22:48, 2 March 2020 (UTC)

- You are absolutely correct in your observation though technically you have the terms reversed. The B10 only contains digits 1 and 0. These are the multipliers to
*give*the B10. Another way to look at it: any number devisable by 9 will have a multiple of 9 digits 1 in it. (It may, and likely will have some variable number of digits 0 too.) If the number n*only*contains digits 9 then it will consist of '1' repeated 9 times the number of 9 digits. (Which is exactly what you stated above, just coming at it from the opposite direction. --Thundergnat (talk) 23:36, 2 March 2020 (UTC)

- Yuppers, I wrongedlyness bidirectionally confuseducated
**B10**with the multiplier. -- Gerard Schildberger (talk) 23:43, 2 March 2020 (UTC)

- Yuppers, I wrongedlyness bidirectionally confuseducated

- I think about prime decomposition of the integer to test, because of the observation that 3 is equivilant to 37 both are factors of 111, so when a number has a factor of 37 I can substitute it by 3, like 2 and 5 both are the factors of 10.

But this is only possible, when both numbers are prime.

7 and 143= 11*13 with 7*(11*13) =1001 so 143*37 = 5291 can't be transformed to 3*7 = 21 with the same result,but into 143*3.

- I think about prime decomposition of the integer to test, because of the observation that 3 is equivilant to 37 both are factors of 111, so when a number has a factor of 37 I can substitute it by 3, like 2 and 5 both are the factors of 10.

B10(21) 10101 : 3[ 111]*7[ 1001] B10(5291) 111111 : 11[ 11]*13[ 1001]*37[ 111] // substitute 37 with 3 B10(429) 111111 : 3[ 111]*11[ 11]*13[ 1001] prime combinations found til 100,000 factor2 can be substituted by factor1 factor1 factor2 B10(factor1) B10(factor2) 2 5 10 10 3 37 111 111 17 653 11101 11101 23 4787 110101 110101 31 3581 111011 111011 41 271 11111 11111 59 186629 11011111 11011111 67 16433 1101011 1101011 73 137 10001 10001 83 1217 101011 101011 107 934673 100010011 100010011 127 86693 11010011 11010011 149 739 110111 110111 151 7351 1110001 1110001 163 6197 1010111 1010111 167 66533 11111011 11111011 181 5531 1001111 1001111 199 557789 111000011 111000011 227 48463 11001101 11001101 239 4649 1111111 1111111 241 461 111101 111101 311 324791 101010001 101010001 331 335381 111011111 111011111 397 27733 11010001 11010001 419 23869 10001111 10001111 421 237791 100110011 100110011 431 234571 101100101 101100101 449 247439 111100111 111100111 457 2190593 1001101001 1001101001 467 214133 100000111 100000111 487 2258953 1100110111 1100110111 521 1938791 1010110111 1010110111 541 18671 10101011 10101011 557 1993 1110101 1110101 587 17053 10010111 10010111 617 1783 1100111 1100111 631 160081 101011111 101011111 881 113621 100100101 100100101 929 1184069 1100000101 1100000101 971 1031 1001101 1001101 1097 1012763 1111001011 1111001011 1123 89057 100011011 100011011 1381 724121 1000011101 1000011101 1511 6691 10110101 10110101 1559 706229 1101011011 1101011011 1567 638233 1000111111 1000111111 1601 69401 111111001 111111001 1777 56843 101010011 101010011 1823 608887 1110001001 1110001001 1949 564449 1100111101 1100111101 2293 480157 1101000001 1101000001 3109 321679 1000100011 1000100011 3313 335077 1110110101 1110110101 3371 299941 1011101111 1011101111 3407 293543 1000101001 1000101001 3461 292141 1011100001 1011100001 3593 306457 1101100001 1101100001 3761 268841 1011111001 1011111001 3889 25999 101110111 101110111 5557 19993 111101101 111101101 6131 179581 1101011111 1101011111 6949 14549 101101001 101101001 6971 145031 1011011101 1011011101 7411 149791 1110101101 1110101101 7573 13337 101001101 101001101 7757 12893 100011001 100011001 7937 13873 110110001 110110001 9199 119699 1101111101 1101111101 9391 11821 111011011 111011011 9829 102859 1011001111 1011001111 9833 11197 110100101 110100101 12589 80309 1011010001 1011010001 25147 43783 1101011101 1101011101 25913 38977 1010011001 1010011001 27739 39659 1100101001 1100101001 30241 33071 1000100111 1000100111

so a factor 934673 can substituted by 107, much less work to be done.But very seldom. For very long B10 3/37 and 41/271 are often factors. --Horst.h 11:21, 3 March 2020 (UTC)~

Hello Host.h, I do not understand everything above, but you seem to say, that a factor of 37 may be replaced by a factor 3... but I find:

# 57 = 19 * 3 B10( 57) = 11001 = n * 193 # 703 = 19 * 37 B10( 703) = 10100001 = n * 14367

what seems to be a (smallish) counter example (there are more). Did I get you wrong? --Heiner (talk) 18:12, 4 April 2020 (UTC)