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.

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

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=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))

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

Sequence in context: A101608 A102853 A304099 * A363654 A189231 A107337

Adjacent sequences: A293387 A293388 A293389 * A293391 A293392 A293393

Keyword

nonn,base

Author

Rémy Sigrist, Oct 08 2017

Status

approved