|
%I #34 Oct 09 2017 00:01:32
%S 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,
%T 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,
%U 3,5,3,7,2,4,4,4,5,5,6,7,3,5,4,7,3,5,6
%N 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.
%C The set of exponents in expression for n as a sum of distinct powers of 2 corresponds to the n-th row of A133457.
%C 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.
%C a(n) >= A000120(n) for any n > 0.
%C Apparently, a(n) = A000120(n) iff n = 0 or n belongs to A100290.
%C a(n) <= A070939(n) for any n >= 0.
%C For any sequence s of distinct nonnegative integers (s(n) being defined for n >= 0):
%C - let D_s be defined for any n > 0 by D_s(n) = a(Sum_{k=0..n-1} 2^s(k)),
%C - then D_s is the discriminator of s as introduced by Arnold, Benkoski, and McCabe in 1985,
%C - D_s(1) = 1,
%C - D_s(n) >= n for any n >= 1,
%C - D_s(n+1) >= D_s(n) for any n >= 1.
%H Robert Israel, <a href="/A293390/b293390.txt">Table of n, a(n) for n = 0..10000</a>
%H Sajed Haque, Jeffrey Shallit, <a href="https://arxiv.org/abs/1605.00092">Discriminators and k-Regular Sequences</a>, arXiv:1605.00092 [cs.DM], 2016.
%F a(2*n) = a(n) for any n >= 0.
%F a(2^k-1) = k for any k >= 0.
%F a(n) = 1 iff n = 2^k for some k >= 0.
%F a(n) = 2 iff n belongs to A173195.
%F a(Sum_{k=1..n} 2^(k^2)) = A016726(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A000069(k)) = A062383(n) for any n >= 1.
%F a(Sum_{k=0..n} 2^(2^k)) = A270097(n) for any n >= 0.
%F a(Sum_{k=1..n} 2^A000045(k+1)) = A270151(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A000041(k)) = A270176(n) for any n >= 1.
%F a(A076793(n)) = A272633(n) for any n >= 0.
%F a(Sum_{k=1..n} 2^A001969(k)) = A272881(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A005823(k)) = A272882(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A000215(k-1)) = A273037(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A000108(k)) = A273041(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A001566(k)) = A273043(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A003095(k)) = A273044(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A000058(k-1)) = A273056(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A002808(k)) = A273062(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^(k!)) = A273064(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^(k^k)) = A273068(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A000110(k)) = A273237(n) for any n >= 1.
%F a(Sum_{k=1..n} 2^A001147(k)) = A273377(n) for any n >= 1.
%e For n=42:
%e - 42 = 2^5 + 2^3 + 2^1,
%e - 5 mod 1 = 3 mod 1,
%e - 5 mod 2 = 3 mod 2,
%e - 5 mod 3, 3 mod 3 and 1 mod 3 are all distinct,
%e - hence a(42) = 3.
%p f:= proc(n) local L,D,k;
%p L:= convert(n,base,2);
%p L:= select(t -> L[t+1]=1, [$0..nops(L)-1]);
%p if nops(L) = 1 then return 1 fi;
%p D:= {seq(seq(L[j]-L[i],i=1..j-1),j=2..nops(L))};
%p D:= `union`(seq(numtheory:-divisors(i),i=D));
%p min({$2..max(D)+1} minus D)
%p end proc:
%p 0, seq(f(i),i=1..100); # _Robert Israel_, Oct 08 2017
%t {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 *)
%o (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))
%Y 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
%K nonn,base
%O 0,4
%A _Rémy Sigrist_, Oct 08 2017
|
