View source for Talk:Minimum positive multiple in base 10 using only 0 and 1

== something's wrong == 
In the task's preamble &nbsp; (in the '''E.G.''' section), &nbsp; the 4<sup>th</sup> multiplication &nbsp; (for a &nbsp; '''B10''' &nbsp; of &nbsp; '''111,111,111'''), &nbsp; the multiplier is incorrect. &nbsp; The multiplier shown would yield a &nbsp; '''B10''' &nbsp; value of &nbsp; '''1,111,111,101''', &nbsp; which isn't the minimum &nbsp; '''B10''' &nbsp; for a &nbsp; '''N''' &nbsp; of &nbsp; '''9'''. &nbsp; &nbsp; -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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 --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 19:19, 29 February 2020 (UTC)

:: That's all well and good. &nbsp; But, the example that I was talking about shows that &nbsp; '''9&nbsp;&times;&nbsp; 123,456,789''' &nbsp; which is the number shown in the task's preamble, &nbsp; not &nbsp;'''9&nbsp;&times;&nbsp;12,345,679'''. &nbsp; &nbsp; -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:32, 29 February 2020 (UTC)
:::: Yes, it was wrong originally but it's correct now. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 19:41, 29 February 2020 (UTC)

::Ah, it looks like an '8' has crept into the multiplier - I'll remove it. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 19:25, 29 February 2020 (UTC)

::: But, &nbsp; "it" &nbsp; could've been an incorrect &nbsp; '''B10''', &nbsp; where the &nbsp; '''B10''' &nbsp; coulda/shoulda/woulda have been &nbsp; '''1,111,111,101''', &nbsp; which would make the original multiplier correct. &nbsp; I could've corrected either value, but one does not want to be accused of vandalism (again). &nbsp; &nbsp; -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:49, 29 February 2020 (UTC)
::::True, but four of us now have come up now with a multiplier of 12,345,679 for n = 9 and the OEIS reference shows a B10 figure of 111,111,111 for that value of 'n', so I'm as sure as I can be that everything is now in order.--[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:00, 29 February 2020 (UTC)

::::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. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 20:17, 1 March 2020 (UTC)

== need for speed ==

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.<BR>
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)<BR>
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.<BR>
Else I start with a High Value HV =B10(j) | j =1..Limit.This HV is shifted by 10^19, but only modular<BR>
so (HV*10^19) MOD N <=> ((HV MOD N)*(10^19 MOD N) MOD N <BR>
(HV MOD N) is alredy calculated,(10^19 MOD N) once for N<BR>
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.<BR>
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.<BR>
Now I am only check if  (N-(HV mod N)) is in the list of first occurence.<br> 
The values upto 9998 are the same as in [[oeis:A004290|OEIS:oeis.org/A004290/b004290.txt]]<br>
There are only 98 values upto 1E6, which are out of range.But first I have to set ModToIdx  : array[0..1000000] of Int32<BR>
--[[User Horst.h|Horst.h]] 17:00, 1 March 2020 (UTC)~

== How does it work "C code for Ed Pegg Jr's 'Binary' Puzzle algorithm" ? ==

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.<BR>
But checking 1..100000 takes real 3m44,890s vs 1m18,507s<BR>

'''But how does it work?'''
<lang c>
//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();
  }
}</lang>
--[[User Horst.h|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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:49, 3 March 2020 (UTC)
:Thanks, that helps allot --[[User Horst.h|Horst.h]] 14:09, 3 March 2020 (UTC)

::On [https://math.stackexchange.com/questions/388165/how-to-find-the-smallest-number-with-just-0-and-1-which-is-divided-by-a-give that link], I see
       10<sup>0</sup> = 1 mod 7 possible sums: 1
       10<sup>1</sup> = 10 = 3 mod 7 possible sums: 1, 3, 4
       10<sup>2</sup> = 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? --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 04:10, 5 March 2020 (UTC)
::: The "3" is from the previous line, the result of 10<sup>1</sup> mod 7. The next power has to multiply that with 10. --[[User:Heiner|Heiner]] ([[User talk:Heiner|talk]]) 04:21, 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<sup>0</sup> = 1   mod 7 = 1 -> possible sums: 1      
       10<sup>1</sup> = 10  mod 7 = 3 -> possible sums: 1, 3, 4
       10<sup>2</sup> = 100 mod 7 = 2 -> possible sums: 1, 2, 3, 4, 5, 6

       I could rewrite this as:  
       10<sup>0</sup> = 1 mod 7 = 1 -> possible sums: 1      
       10<sup>1</sup> = 1<sup>1</sup>0 = 10 mod 7 = 3 -> possible sums: 1, 3, 4
       10<sup>2</sup> = 1<sup>1</sup>0<sup>3</sup>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<sup>1</sup>0     -> 3
       1<sup>1</sup>1     -> 4
       
       1<sup>1</sup>0<sup>3</sup>0   -> 2
       1<sup>1</sup>0<sup>3</sup>1   -> 3
       1<sup>1</sup>1<sup>4</sup>0   -> 5
       1<sup>1</sup>1<sup>4</sup>1   -> 6
       
       1<sup>1</sup>0<sup>1</sup>0<sup>2</sup>0 -> 6
       1<sup>1</sup>0<sup>1</sup>0<sup>2</sup>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.
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 15:00, 14 March 2020 (UTC)

== general observations ==

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''', &nbsp; and change the last eight to a nine.
::: For '''99''',  the '''B10''' digits are '''1122334455667788''', &nbsp; and change the last eight to a nine.
::: For '''999''',  the '''B10''' digits are '''111222333444555666777888''', &nbsp; and change the last eight to a nine.
::: For '''9999''',  the '''B10''' digits are '''11112222333344445555666677778888''', &nbsp; and change the last eight to a nine.


I'm sure there is a more elegant way of expressing this, &nbsp; but I think showing is better than telling &nbsp; (the pattern seems obvious enough). &nbsp; &nbsp; -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 23:36, 2 March 2020 (UTC)

:: Yuppers, I wrongedlyness bidirectionally confuseducated '''B10''' with the multiplier. &nbsp; &nbsp; -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 23:43, 2 March 2020 (UTC)

::: 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.<BR>But this is only possible, when both numbers are prime.<BR>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.
<pre style="height:150px">
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</pre>
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. 
--[[user Horst.h|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? --[[User:Heiner|Heiner]] ([[User talk:Heiner|talk]]) 18:12, 4 April 2020 (UTC)