Talk:Minimum positive multiple in base 10 using only 0 and 1: Difference between revisions
Content added Content deleted
(→How does it work "C code for Ed Pegg Jr's 'Binary' Puzzle algorithm" ?: from previous line) |
|||
Line 105: | Line 105: | ||
::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) |
::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 "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>2</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 -> 7 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 == |
== general observations == |