login
A293390
Least m such that the exponents in expression for n as a sum of distinct powers of 2 are pairwise distinct mod m; a(0) = 0 by convention.
2
0, 1, 1, 2, 1, 3, 2, 3, 1, 2, 3, 4, 2, 4, 3, 4, 1, 3, 2, 5, 3, 3, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 1, 2, 3, 3, 2, 4, 5, 6, 3, 4, 3, 6, 4, 4, 5, 6, 2, 3, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 1, 4, 2, 4, 3, 5, 3, 7, 2, 4, 4, 4, 5, 5, 6, 7, 3, 5, 4, 7, 3, 5, 6
OFFSET
0,4
COMMENTS
The set of exponents in expression for n as a sum of distinct powers of 2 corresponds to the n-th row of A133457.
The sum of digits of n in base 2^a(n), say s, can be computed without carry in base 2; the Hamming weight of s equals the Hamming weight of n.
a(n) >= A000120(n) for any n > 0.
Apparently, a(n) = A000120(n) iff n = 0 or n belongs to A100290.
a(n) <= A070939(n) for any n >= 0.
For any sequence s of distinct nonnegative integers (s(n) being defined for n >= 0):
- let D_s be defined for any n > 0 by D_s(n) = a(Sum_{k=0..n-1} 2^s(k)),
- then D_s is the discriminator of s as introduced by Arnold, Benkoski, and McCabe in 1985,
- D_s(1) = 1,
- D_s(n) >= n for any n >= 1,
- D_s(n+1) >= D_s(n) for any n >= 1.
LINKS
Sajed Haque, Jeffrey Shallit, Discriminators and k-Regular Sequences, arXiv:1605.00092 [cs.DM], 2016.
FORMULA
a(2*n) = a(n) for any n >= 0.
a(2^k-1) = k for any k >= 0.
a(n) = 1 iff n = 2^k for some k >= 0.
a(n) = 2 iff n belongs to A173195.
a(Sum_{k=1..n} 2^(k^2)) = A016726(n) for any n >= 1.
a(Sum_{k=1..n} 2^A000069(k)) = A062383(n) for any n >= 1.
a(Sum_{k=0..n} 2^(2^k)) = A270097(n) for any n >= 0.
a(Sum_{k=1..n} 2^A000045(k+1)) = A270151(n) for any n >= 1.
a(Sum_{k=1..n} 2^A000041(k)) = A270176(n) for any n >= 1.
a(A076793(n)) = A272633(n) for any n >= 0.
a(Sum_{k=1..n} 2^A001969(k)) = A272881(n) for any n >= 1.
a(Sum_{k=1..n} 2^A005823(k)) = A272882(n) for any n >= 1.
a(Sum_{k=1..n} 2^A000215(k-1)) = A273037(n) for any n >= 1.
a(Sum_{k=1..n} 2^A000108(k)) = A273041(n) for any n >= 1.
a(Sum_{k=1..n} 2^A001566(k)) = A273043(n) for any n >= 1.
a(Sum_{k=1..n} 2^A003095(k)) = A273044(n) for any n >= 1.
a(Sum_{k=1..n} 2^A000058(k-1)) = A273056(n) for any n >= 1.
a(Sum_{k=1..n} 2^A002808(k)) = A273062(n) for any n >= 1.
a(Sum_{k=1..n} 2^(k!)) = A273064(n) for any n >= 1.
a(Sum_{k=1..n} 2^(k^k)) = A273068(n) for any n >= 1.
a(Sum_{k=1..n} 2^A000110(k)) = A273237(n) for any n >= 1.
a(Sum_{k=1..n} 2^A001147(k)) = A273377(n) for any n >= 1.
EXAMPLE
For n=42:
- 42 = 2^5 + 2^3 + 2^1,
- 5 mod 1 = 3 mod 1,
- 5 mod 2 = 3 mod 2,
- 5 mod 3, 3 mod 3 and 1 mod 3 are all distinct,
- hence a(42) = 3.
MAPLE
f:= proc(n) local L, D, k;
L:= convert(n, base, 2);
L:= select(t -> L[t+1]=1, [$0..nops(L)-1]);
if nops(L) = 1 then return 1 fi;
D:= {seq(seq(L[j]-L[i], i=1..j-1), j=2..nops(L))};
D:= `union`(seq(numtheory:-divisors(i), i=D));
min({$2..max(D)+1} minus D)
end proc:
0, seq(f(i), i=1..100); # Robert Israel, Oct 08 2017
MATHEMATICA
{0}~Join~Table[Function[r, SelectFirst[Range@ 10, Length@ Union@ Mod[r, #] == Length@ r &]][Join @@ Position[#, 1] - 1 &@ Reverse@ IntegerDigits[n, 2]], {n, 86}] (* Michael De Vlieger, Oct 08 2017 *)
PROG
(PARI) a(n) = if (n, my (d=Vecrev(binary(n)), x = []); for (i=1, #d, if (d[i], x = concat(x, i-1))); for (m=1, oo, if (#Set(vector(#x, i, x[i]%m))==#x, return (m))), return (0))
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Oct 08 2017
STATUS
approved