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 17:00, 1 March 2020
, 4 years ago→need for speed: new section
(Another comment.) |
(→need for speed: new section) |
||
Line 10:
::: 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). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:49, 29 February 2020 (UTC)
::::True, but four of us now have come up now with a multiplier of 12,345,679 for n = 9 and the OEIS reference shows a B10 figure of 111,111,111 for that value of 'n', so I'm as sure as I can be that everything is now in order.--[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:00, 29 February 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.<BR>
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)<BR>
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.<BR>
Else I start with a High Value HV =B10(j) | j =1..Limit.This HV is shifted by 10^19, but only modular<BR>
so (HV*10^19) MOD N <=> ((HV MOD N)*(10^19 MOD N) MOD N <BR>
(HV MOD N) is alredy calculated,(10^19 MOD N) once for N<BR>
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.<BR>
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.<BR>
Now I am only check if (N-(HV mod N)) is in the list of first occurence.<br>
The values upto 9998 are the same as in [[oeis:A004290|OEIS:oeis.org/A004290/b004290.txt]]<br>
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)~
| |||