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

0, 1, 2, 4, 3, 8, 5, 16, 32, 9, 6, 64, 128, 10, 17, 256, 33, 512, 7, 1024, 18, 65, 12, 2048, 129, 34, 4096, 11, 8192, 257, 16384, 66, 32768, 20, 130, 513, 65536, 131072, 1025, 36, 19, 262144, 258, 13, 524288, 1048576, 2049, 24, 35, 2097152, 4097, 4194304, 68

Offset: 1

Author

Antti Karttunen, Jul 14 1999

Keywords

• easy
• nonn

Comments

Permutation of nonnegative integers. Note the indexing, the domain starts from 1, although the range includes also 0.

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

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

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

Examples

			From _Gus Wiseman_, Nov 30 2019: (Start)
The sequence of squarefree numbers together with their prime indices (A329631) and the number a(n) with those binary indices begins:
   1 ->  {}      ->   0
   2 ->  {1}     ->   1
   3 ->  {2}     ->   2
   5 ->  {3}     ->   4
   6 ->  {1,2}   ->   3
   7 ->  {4}     ->   8
  10 ->  {1,3}   ->   5
  11 ->  {5}     ->  16
  13 ->  {6}     ->  32
  14 ->  {1,4}   ->   9
  15 ->  {2,3}   ->   6
  17 ->  {7}     ->  64
  19 ->  {8}     -> 128
  21 ->  {2,4}   ->  10
  22 ->  {1,5}   ->  17
  23 ->  {9}     -> 256
  26 ->  {1,6}   ->  33
  29 ->  {10}    -> 512
  30 ->  {1,2,3} ->   7
(End)
		

Links

• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A246353 (see also A064273).

Cf. A005117, A048639, A048640, A048623.

Cf. A019565.

A similar encoding of set-systems is A329661.

Cf. A000120, A048793, A056239, A070939, A072047, A112798, A329631.

Cf. A087207.

Programs

Maple

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

Mathematica

Join[{0}, Total[2^(PrimePi[FactorInteger[#][[All, 1]]] - 1)]& /@ Select[ Range[2, 100], SquareFreeQ]] (* Jean-François Alcover, Mar 15 2016 *)

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

Python

from math import isqrt
from sympy import mobius, primepi, primefactors
def A048672(n):
    if n == 1: return 0
    def f(x): return int(n-sum(mobius(k)*(x//k**2) for k in range(2, isqrt(x)+1)))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return sum(1<Chai Wah Wu, Feb 22 2025

Formula

a(n) = 2^(i1-1)+2^(i2-1)+...+2^(iz-1), where A005117(n) = p_i1*p_i2*p_i3*...*p_iz.

A019565(a(n)) = A005117(n). - Peter Munn, Nov 19 2019

A000120(a(n)) = A072047(n). - Gus Wiseman, Nov 30 2019

a(n) = A087207(A005117(n)). - Flávio V. Fernandes, Feb 26 2025