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++){
//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> --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)
- I've added a reference "How to find Minimum Positive Multiple in base 10 using only 0 and 1" which I think helps.--Nigel Galloway (talk) 13:49, 3 March 2020 (UTC)
- Thanks, that helps allot --Horst.h 14:09, 3 March 2020 (UTC)
- On that link, I see
100 = 1 mod 7 possible sums: 1
101 = 10 = 3 mod 7 possible sums: 1, 3, 4
102 = 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? --Pete Lomax (talk) 04:10, 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:
100 = 1 mod 7 = 1 -> possible sums: 1
101 = 10 mod 7 = 3 -> possible sums: 1, 3, 4
102 = 100 mod 7 = 2 -> possible sums: 1, 2, 3, 4, 5, 6
I could rewrite this as:
100 = 1 mod 7 = 1 -> possible sums: 1
101 = 110 = 10 mod 7 = 3 -> possible sums: 1, 3, 4
102 = 11030 = 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
110 -> 3
111 -> 4
11030 -> 2
11031 -> 3
11140 -> 5
11141 -> 6
1101020 -> 6
1101021 -> 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.
--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, 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)
- 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. --Thundergnat (talk) 23:36, 2 March 2020 (UTC)
- Yuppers, I wrongedlyness bidirectionally confuseducated B10 with the multiplier. -- 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.
But this is only possible, when both numbers are prime.
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.
- 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.
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
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. --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? --Heiner (talk) 18:12, 4 April 2020 (UTC)