Talk:Minimum positive multiple in base 10 using only 0 and 1: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 18:14, 4 April 2020

something's wrong

In the task's preamble (in the E.G. section), the 4^th 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)

Yes, it was wrong originally but it's correct now. --PureFox (talk) 19:41, 29 February 2020 (UTC)

Ah, it looks like an '8' has crept into the multiplier - I'll remove it. --PureFox (talk) 19:25, 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)

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.--PureFox (talk) 20:00, 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

      10⁰ = 1 mod 7 possible sums: 1
      10¹ = 10 = 3 mod 7 possible sums: 1, 3, 4
      10² = 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 "3" is from the previous line, the result of 10¹ mod 7. The next power has to multiply that with 10. --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⁰ = 1   mod 7 = 1 -> possible sums: 1      
      10¹ = 10  mod 7 = 3 -> possible sums: 1, 3, 4
      10² = 100 mod 7 = 2 -> possible sums: 1, 2, 3, 4, 5, 6

      I could rewrite this as:  
      10⁰ = 1 mod 7 = 1 -> possible sums: 1      
      10¹ = 1¹0 = 10 mod 7 = 3 -> possible sums: 1, 3, 4
      10² = 1¹0³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¹0     -> 3
      1¹1     -> 4
      
      1¹0³0   -> 2
      1¹0³1   -> 3
      1¹1⁴0   -> 5
      1¹1⁴1   -> 6
      
      1¹0¹0²0 -> 6
      1¹0¹0²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.

--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.

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)