login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
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 (list; graph; refs; listen; history; text; internal format)
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 * A189231 A107337 A066376

Adjacent sequences:  A293387 A293388 A293389 * A293391 A293392 A293393

KEYWORD

nonn,base

AUTHOR

Rémy Sigrist, Oct 08 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 11:14 EDT 2021. Contains 348211 sequences. (Running on oeis4.)