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 )

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