login
A337623
a(n) is the least positive multiple of 2*n-1 containing only the digits 0 and 1 in base n.
1
1, 3, 10, 21, 126, 253, 351, 585, 6562, 11001, 14763, 22609, 28575, 41175, 50866, 69905, 1419858, 1994545, 2482959, 3368001, 4084543, 5388373, 6449040, 8308801, 9765651, 12338379, 14368618, 17847005, 20512020, 25110931, 28659935, 34636833, 1291467970, 1590239841
OFFSET
1,2
COMMENTS
Based on test for divisibility, where in base n the number n*a + b is divisible by x if and only if a + b*m is also divisible by x, and a multiple of x is one less than m*n.
Example:
10a + b |13
10a + b + 13*b*t |13 (Add multiple of 13)
10a + b(1 + 13t) |13 (Rearrange)
10a + b(1 + 13*3) |13 (Let t be 3)
a + b*4 | 13 (Divide by base (10). 13 is coprime to 10, so divisibility to 13 is contained) |13
Specifically (in base n): a*n + b is divisible by 2n-1 if and only if a + b*2 is also divisible by 2n - 1.
By doing the "10a + b => a + 2b" process (that preserves divisibility by 2n-1) iteratively, you get reversed binary representation.
It's still the lowest case even after reversing digits, since any higher multiple in base 2 will always add digits.
FORMULA
1. Write 2n-1 in binary.
2. Reverse order of digits.
3. Read as number in base n.
Pseudo code: read_base_n(reverse(write_base_2(2n-1))).
a(n) = (2*n-1)*A337624(n).
EXAMPLE
Base 10:
2n - 1 = 19.
19 in binary: 10011
Reversed: 11001
11001 is thus the lowest number in base 10 divisible by 19 that contains only the digits 0 and 1.
PROG
(PARI) a(n) = if (n==1, 1, fromdigits(Vecrev(binary(2*n-1)), n)); \\ Michel Marcus, Sep 09 2020
CROSSREFS
Cf. A337624.
Sequence in context: A373081 A120109 A286067 * A158030 A068082 A058077
KEYWORD
nonn,base,easy
AUTHOR
Egil Sandnes, Sep 09 2020
STATUS
approved