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

something's wrong

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)

Yes, it was wrong originally but it's correct now. --PureFox (talk) 19:41, 29 February 2020 (UTC)

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

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)

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.--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. --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.
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" ?

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? <lang c> //copyright http://www.mathpuzzle.com/Binary.html //slightly modified (runtime 6m -> 3,75m )

1. include <stdio.h>
2. 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++){
    val[x]=ten;
    int mod = ten;
    for(j=0;j<n1;j++){
      if(pow[j]&&pow[j]!=x){
        if (!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> --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)

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

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)