login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A087207 A binary representation of the primes that divide a number, shown in decimal. 30
0, 1, 2, 1, 4, 3, 8, 1, 2, 5, 16, 3, 32, 9, 6, 1, 64, 3, 128, 5, 10, 17, 256, 3, 4, 33, 2, 9, 512, 7, 1024, 1, 18, 65, 12, 3, 2048, 129, 34, 5, 4096, 11, 8192, 17, 6, 257, 16384, 3, 8, 5, 66, 33, 32768, 3, 20, 9, 130, 513, 65536, 7, 131072, 1025, 10, 1, 36, 19, 262144, 65, 258 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

The binary representation of a(n) shows which prime numbers divide n, but not the multiplicities. a(2)=1, a(3)=10, a(4)=1, a(5)=100, a(6)=11, a(10)=101, a(30)=111, etc.

For n > 1, a(n) gives the (one-based) index of the column where n is located in array A285321. A008479 gives the other index. - Antti Karttunen, Apr 17 2017

From Antti Karttunen, Jun 18 & 20 2017: (Start)

A268335 gives all n such that a(n) = A248663(n); the squarefree numbers (A005117) are all the n such that a(n) = A285330(n) = A048675(n).

For all n > 1 for which the value of A285331(n) is well-defined, we have A285331(a(n)) <= floor(A285331(n)/2), because then n is included in the binary tree A285332 and a(n) is one of its ancestors (in that tree), and thus must be at least one step nearer to its root than n itself.

Conjecture: Starting at any n and iterating the map n -> a(n), we will always reach 0 (see A288569). This conjecture is equivalent to the conjecture that at any n that is neither a prime nor a power of two, we will eventually hit a prime number (which then becomes a power of two in the next iteration). If this conjecture is false then sequence A285332 cannot be a permutation of natural numbers. On the other hand, if the conjecture is true, then A285332 must be a permutation of natural numbers, because all primes and powers of 2 occur in definite positions in that tree. This conjecture also implies the conjectures made in A019565 and A285320 that essentially claim that there are neither finite nor infinite cycles in A019565.

If there are any 2-cycles in this sequence, then both terms of the cycle should be present in A286611 and the larger one should be present in A286612.

(End)

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..10000 [First 1000 terms from T. D. Noe]

Index entries for sequences related to binary expansion of n

Index entries for sequences computed from indices in prime factorization

FORMULA

Additive with a(p^e) = 2^(i-1) where p is the i-th prime. - Vladeta Jovovic, Oct 29 2003

a(n) gives the m such that A019565(m) = A007947(n). - Naohiro Nomoto, Oct 30 2003

A000120(a(n)) = A001221(n); a(n) = Sum(2^(A049084(p)-1): p prime-factor of n). - Reinhard Zumkeller, Nov 30 2003

G.f.: Sum_{k>=1} 2^(k-1)*x^prime(k)/(1-x^prime(k). [Franklin T. Adams-Watters, Sep 01 2009]

From Antti Karttunen, Apr 17 2017, Jun 19 2017 & Dec 06 2018: (Start)

a(n) = A048675(A007947(n)).

a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A028234(n)).

A000035(a(n)) = 1 - A000035(n). [a(n) and n are of opposite parity.]

A248663(n) <= a(n) <= A048675(n). [XOR-, OR- and +-variants.]

a(A293214(n)) = A218403(n).

a(A293442(n)) = A267116(n).

A069010(a(n)) = A287170(n).

A007088(a(n)) = A276379(n).

A038374(a(n)) = A300820(n) for n >= 1.

(End)

EXAMPLE

a(38) = 129 because 38 = 2*19 = prime(1)*prime(8) and 129 = 2^0 + 2^7 (in binary 10000001).

a(140) = 13, binary 1101 because 140 is divisible by the first, third and fourth primes and 2^(1-1) + 2^(3-1) + 2^(4-1) = 13.

MATHEMATICA

a[n_] := Total[ 2^(PrimePi /@ FactorInteger[n][[All, 1]] - 1)]; a[1] = 0; Table[a[n], {n, 1, 69}] (* Jean-Fran├žois Alcover, Dec 12 2011 *)

PROG

(Haskell)

a087207 = sum . map ((2 ^) . (subtract 1) . a049084) . a027748_row

-- Reinhard Zumkeller, Jul 16 2013

(PARI) a(n) = {if (n==1, 0, my(f=factor(n), v = []); forprime(p=2, vecmax(f[, 1]), v = concat(v, vecsearch(f[, 1], p)!=0); ); fromdigits(Vecrev(v), 2)); } \\ Michel Marcus, Jun 05 2017

(PARI) A087207(n)=vecsum(apply(p->1<<primepi(p-1), factor(n)[, 1])) \\ Significantly faster than using sum(...). - M. F. Hasler, Jun 23 2017

(Python)

from sympy import factorint, primepi

def a(n):

    f=factorint(n)

    return sum([2**primepi(i - 1) for i in f])

print [a(n) for n in xrange(1, 101)] # Indranil Ghosh, Jun 06 2017

(Scheme)

(definec (A087207 n) (if (= 1 n) 0 (+ (A000079 (+ -1 (A055396 n))) (A087207 (A028234 n))))) ;; This uses memoization-macro definec

(define (A087207 n) (A048675 (A007947 n))) ;; Needs code from A007947 and A048675. - Antti Karttunen, Jun 19 2017

CROSSREFS

For partial sums see A288566.

Cf. A000040, A000120, A001221, A005117, A007947, A008479, A019565, A027748, A048675, A055396, A248663, A285320, A285321, A285329, A285330, A285332, A288569, A289271, A297404.

Cf. A276379 (same sequence shown in base 2).

Cf. A286608 (numbers n for which a(n) < n), A286609 (n for which a(n) > n), and also A286611, A286612.

Sequence in context: A058354 A085930 A258863 * A179206 A074987 A294096

Adjacent sequences:  A087204 A087205 A087206 * A087208 A087209 A087210

KEYWORD

nonn,base,nice

AUTHOR

Mitch Cervinka (puritan(AT)planetkc.com), Oct 26 2003

EXTENSIONS

More terms from Don Reble, Ray Chandler and Naohiro Nomoto, Oct 28 2003

Name clarified by Antti Karttunen, Jun 18 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 March 20 05:34 EDT 2019. Contains 321344 sequences. (Running on oeis4.)