cp's OEIS Frontend

A048672 Binary encoding of squarefree numbers (A005117): A048640(n)/2.

%I A048672 #42 Feb 26 2025 06:34:43
%S A048672 0,1,2,4,3,8,5,16,32,9,6,64,128,10,17,256,33,512,7,1024,18,65,12,2048,
%T A048672 129,34,4096,11,8192,257,16384,66,32768,20,130,513,65536,131072,1025,
%U A048672 36,19,262144,258,13,524288,1048576,2049,24,35,2097152,4097,4194304,68
%N A048672 Binary encoding of squarefree numbers (A005117): A048640(n)/2.
%C A048672 Permutation of nonnegative integers. Note the indexing, the domain starts from 1, although the range includes also 0.
%C A048672 A246353 gives the inverse of this sequence, in a sense that a(A246353(n)) = n for all n >= 0, and A246353(a(n)) = n for all n >= 1. When one is subtracted from the latter, another permutation of nonnegative integers is obtained: A064273. - _Antti Karttunen_, Aug 23 2014 based on comment from _Howard A. Landman_, Sep 25 2001
%C A048672 Also index of n-th term of A019565 when its terms are sorted in increasing order. For example: a(6) = 8. The smallest values of A019565 are 1,2,3,5,6,7 . The 6th is 7 which is A019565(8). - Philippe Lallouet (philip.lallouet(AT)orange.fr), Apr 28 2008
%C A048672 a(n) is the number whose binary indices are the prime indices of the n-th squarefree number (row n of A329631), where a binary index of n is any position of a 1 in its reversed binary expansion, and a prime index of n is a number m such that prime(m) divides n. The binary indices of n are row n of A048793, while the prime indices of n are row n of A112798. - _Gus Wiseman_, Nov 30 2019
%H A048672 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A048672 a(n) = 2^(i1-1)+2^(i2-1)+...+2^(iz-1), where A005117(n) = p_i1*p_i2*p_i3*...*p_iz.
%F A048672 A019565(a(n)) = A005117(n). - _Peter Munn_, Nov 19 2019
%F A048672 A000120(a(n)) = A072047(n). - _Gus Wiseman_, Nov 30 2019
%F A048672 a(n) = A087207(A005117(n)). - _Flávio V. Fernandes_, Feb 26 2025
%e A048672 From _Gus Wiseman_, Nov 30 2019: (Start)
%e A048672 The sequence of squarefree numbers together with their prime indices (A329631) and the number a(n) with those binary indices begins:
%e A048672    1 ->  {}      ->   0
%e A048672    2 ->  {1}     ->   1
%e A048672    3 ->  {2}     ->   2
%e A048672    5 ->  {3}     ->   4
%e A048672    6 ->  {1,2}   ->   3
%e A048672    7 ->  {4}     ->   8
%e A048672   10 ->  {1,3}   ->   5
%e A048672   11 ->  {5}     ->  16
%e A048672   13 ->  {6}     ->  32
%e A048672   14 ->  {1,4}   ->   9
%e A048672   15 ->  {2,3}   ->   6
%e A048672   17 ->  {7}     ->  64
%e A048672   19 ->  {8}     -> 128
%e A048672   21 ->  {2,4}   ->  10
%e A048672   22 ->  {1,5}   ->  17
%e A048672   23 ->  {9}     -> 256
%e A048672   26 ->  {1,6}   ->  33
%e A048672   29 ->  {10}    -> 512
%e A048672   30 ->  {1,2,3} ->   7
%e A048672 (End)
%p A048672 encode_sqrfrees := proc(upto_n) local b,i; b := [ ]; for i from 1 to upto_n do if(0 <> mobius(i)) then b := [ op(b), bef(i) ]; fi; od: RETURN(b); end; # see A048623 for bef
%t A048672 Join[{0}, Total[2^(PrimePi[FactorInteger[#][[All, 1]]] - 1)]& /@ Select[ Range[2, 100], SquareFreeQ]] (* _Jean-François Alcover_, Mar 15 2016 *)
%o A048672 (PARI) lista(nn) = {for (n=1, nn, if (issquarefree(n), if (n==1, x = 0, f = factor(n); x = sum(k=1, #f~, 2^(primepi(f[k, 1])-1))); print1(x, ", "); ); ); } \\ _Michel Marcus_, Oct 02 2015
%o A048672 (Python)
%o A048672 from math import isqrt
%o A048672 from sympy import mobius, primepi, primefactors
%o A048672 def A048672(n):
%o A048672     if n == 1: return 0
%o A048672     def f(x): return int(n-sum(mobius(k)*(x//k**2) for k in range(2, isqrt(x)+1)))
%o A048672     m, k = n, f(n)
%o A048672     while m != k: m, k = k, f(k)
%o A048672     return sum(1<<primepi(p)-1 for p in primefactors(m)) # _Chai Wah Wu_, Feb 22 2025
%Y A048672 Inverse: A246353 (see also A064273).
%Y A048672 Cf. A005117, A048639, A048640, A048623.
%Y A048672 Cf. A019565.
%Y A048672 A similar encoding of set-systems is A329661.
%Y A048672 Cf. A000120, A048793, A056239, A070939, A072047, A112798, A329631.
%Y A048672 Cf. A087207.
%K A048672 easy,nonn
%O A048672 1,3
%A A048672 _Antti Karttunen_, Jul 14 1999