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 18:14, 4 April 2020
, 4 years ago→general observations: replacing 37 by 3 does not work
(→general observations: replacing 37 by 3 does not work) |
|||
| (15 intermediate revisions by 6 users not shown) | |||
Line 53:
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])
mod++;
if(mod==num)
mod =0;
}
if(!pow[ten])
pow[ten]=
ten=(10*ten)%num;
if(pow[0])
break;
Line 95:
: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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:49, 3 March 2020 (UTC)
:Thanks, that helps allot --[[User Horst.h|Horst.h]] 14:09, 3 March 2020 (UTC)
::On [https://math.stackexchange.com/questions/388165/how-to-find-the-smallest-number-with-just-0-and-1-which-is-divided-by-a-give that link], I see
10<sup>0</sup> = 1 mod 7 possible sums: 1
10<sup>1</sup> = 10 = 3 mod 7 possible sums: 1, 3, 4
10<sup>2</sup> = 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? --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 04:10, 5 March 2020 (UTC)
::: The "3" is from the previous line, the result of 10<sup>1</sup> mod 7. The next power has to multiply that with 10. --[[User:Heiner|Heiner]] ([[User talk:Heiner|talk]]) 04:21, 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:
10<sup>0</sup> = 1 mod 7 = 1 -> possible sums: 1
10<sup>1</sup> = 10 mod 7 = 3 -> possible sums: 1, 3, 4
10<sup>2</sup> = 100 mod 7 = 2 -> possible sums: 1, 2, 3, 4, 5, 6
I could rewrite this as:
10<sup>0</sup> = 1 mod 7 = 1 -> possible sums: 1
10<sup>1</sup> = 1<sup>1</sup>0 = 10 mod 7 = 3 -> possible sums: 1, 3, 4
10<sup>2</sup> = 1<sup>1</sup>0<sup>3</sup>0 = 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
1<sup>1</sup>0 -> 3
1<sup>1</sup>1 -> 4
1<sup>1</sup>0<sup>3</sup>0 -> 2
1<sup>1</sup>0<sup>3</sup>1 -> 3
1<sup>1</sup>1<sup>4</sup>0 -> 5
1<sup>1</sup>1<sup>4</sup>1 -> 6
1<sup>1</sup>0<sup>1</sup>0<sup>2</sup>0 -> 6
1<sup>1</sup>0<sup>1</sup>0<sup>2</sup>1 -> 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.
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk: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). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 23:36, 2 March 2020 (UTC)
:: Yuppers, I wrongedlyness bidirectionally confuseducated '''B10''' with the multiplier. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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.<BR>But this is only possible, when both numbers are prime.<BR>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.
<pre style="height:150px">
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</pre>
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.
--[[user Horst.h|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? --[[User:Heiner|Heiner]] ([[User talk:Heiner|talk]]) 18:12, 4 April 2020 (UTC)
| |||