Anonymous user
Talk:Minimum positive multiple in base 10 using only 0 and 1: Difference between revisions
Talk:Minimum positive multiple in base 10 using only 0 and 1 (view source)
Revision as of 14:10, 2 March 2020
, 4 years ago→How does it work "C code for Ed Pegg Jr's 'Binary' Puzzle algorithm" ?: new section
Thundergnat (talk | contribs) (→something's wrong: Thanks for fixing my errors.) |
|||
Line 29:
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++){
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>
--[[User Horst.h|Horst.h]] 14:10, 2 March 2020 (UTC)~
| |||