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.
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
Robert Israel, Table of n, a(n) for n = 0..10000
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=0..n} 2^(2^k)) = A270097(n) for any n >= 0.
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.
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))
CROSSREFS
Cf. A000041, A000045, A000058, A000069, A000108, A000110, A000120, A000215, A001147, A001566, A001969, A002808, A003095, A005823, A016726, A062383, A070939, A076793, A100290, A133457, A173195, A270097, A270151, A270176, A272633, A272881, A272882, A273037, A273041, A273043, A273044, A273056, A273062, A273064, A273068, A273237, A273377
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Oct 08 2017
STATUS
approved