cp's OEIS Frontend

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.

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