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 4th 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)
- 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)
- 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)~
- No idea, however I had four (unrelated) minor insights: 1) B10(n) where n is all-nines is all-ones. 2) No smallest multiplier ends with 0. 3) B10(2n) is either B10(n) 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}. None of those really help explain anything though. --Pete Lomax (talk) 15:36, 2 March 2020 (UTC)