A285329 -id:A285329 - cp's OEIS frontend

A087207 A binary representation of the primes that divide a number, shown in decimal.

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

Offset: 1

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

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)
Binary rank of the distinct prime indices of n, where the binary rank of an integer partition y is given by Sum_i 2^(y_i-1). For all prime indices (with multiplicity) we have A048675. - Gus Wiseman, May 25 2024

			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.

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

For partial sums see A288566.
Cf. A000040, A000120, A001221, A005117, A008479, A019565, A055396, A285320, A285321, A285329, A285330, A285332.
Sequences with related definitions: A007947, A008472, A027748, A048675, A248663, A276379 (same sequence shown in base 2), A288569, A289271, A297404.
Cf. A286608 (numbers n for which a(n) < n), A286609 (n for which a(n) > n), and also A286611, A286612.
A003986, A003961, A059896 are used to express relationship between terms of this sequence.
Related to A267116 via A225546.
Positions of particular values are: A000079\{1} (1), A000244\{1} (2), A033845 (3), A000351\{1} (4), A033846 (5), A033849 (6), A143207 (7), A000420\{1} (8), A033847 (9), A033850 (10), A033851 (12), A147576 (14), A147571 (15), A001020\{1} (16), A033848 (17).
A048675 gives binary rank of prime indices.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, length A001222, reverse A296150, sum A056239.
Binary indices (listed A048793):
- length A000120, complement A023416
- min A001511, opposite A000012
- sum A029931, product A096111
- max A029837 or A070939, opposite A070940
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
- opposite A371572, sum A230877
Cf. A000720, A005940, A018819, A023506, A071814, A225620, A277319, A277905, A304818, A372689, A372890.

a087207 = sum . map ((2 ^) . (subtract 1) . a049084) . a027748_row
-- Reinhard Zumkeller, Jul 16 2013

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 *)

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

A087207(n)=vecsum(apply(p->1<M. F. Hasler, Jun 23 2017

from sympy import factorint, primepi
def a(n):
    return sum(2**primepi(i - 1) for i in factorint(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 06 2017

(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

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)
From Peter Munn, Jan 08 2020: (Start)
a(A059896(n,k)) = a(n) OR a(k) = A003986(a(n), a(k)).
a(A003961(n)) = 2*a(n).
a(n^2) = a(n).
a(n) = A267116(A225546(n)).
a(A225546(n)) = A267116(n).
(End)

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

Name clarified by Antti Karttunen, Jun 18 2017

A008479 Number of numbers <= n with same prime factors as n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 4, 2, 1, 3, 2, 1, 1, 1, 5, 1, 1, 1, 5, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 6, 2, 4, 1, 2, 1, 7, 1, 3, 1, 1, 1, 2, 1, 1, 2, 6, 1, 1, 1, 2, 1, 1, 1, 8, 1, 1, 3, 2, 1, 1, 1, 5, 4, 1, 1, 2, 1, 1, 1, 3, 1, 3, 1, 2, 1, 1, 1, 9

Offset: 1

Jeffrey Shallit, Olivier Gérard

For n > 1, a(n) gives the (one-based) index of the row where n is located in arrays A284311 and A285321 or respectively, index of the column where n is in A284457. A285329 gives the other index. - Antti Karttunen, Apr 17 2017

T. D. Noe, Table of n, a(n) for n = 1..10000
Paul Erdős and T. Motzkin, Problem 5735, Amer. Math. Monthly, 78 (1971), 680-681. (Incorrect solution!)
H. N. Shapiro, Problem 5735, Amer. Math. Monthly, 97 (1990), 937.

Cf. A005117 (positions of ones), A005361, A007947, A008683, A010846, A284311, A284457, A285321, A285328, A285329.

N:= 100: # to get a(1)..a(N)
V:= Vector(N):
V[1]:= 1:
for n from 2 to N do
  if V[n] = 0 then
   S:= {n};
   for p in numtheory:-factorset(n) do
     S := S union {seq(seq(s*p^k,k=1..floor(log[p](N/s))),s=S)};
   od:
   S:= sort(convert(S,list));
   for k from 1 to nops(S) do V[S[k]]:= k od:
fi
od:
convert(V,list); # Robert Israel, May 20 2016

PkTbl=Prepend[ Array[ Times @@ First[ Transpose[ FactorInteger[ # ] ] ]&, 100, 2 ], 1 ];1+Array[ Count[ Take[ PkTbl, #-1 ], PkTbl[ [ # ] ] ]&, Length[ PkTbl ] ]
Count[#, k_ /; k == Last@ #] & /@ Function[s, Take[s, #] & /@ Range@ Length@ s]@ Array[Map[First, FactorInteger@ #] &, 120] (* or *)
Table[Sum[(Floor[n^k/k] - Floor[(n^k - 1)/k]) (Floor[k^n/n] - Floor[(k^n - 1)/n]), {k, n}], {n, 120}] (* Michael De Vlieger, May 20 2016 *)

a(n)=my(f=factor(n)[,1], s); forvec(v=vector(#f, i, [1, logint(n, f[i])]), if(prod(i=1, #f, f[i]^v[i])<=n, s++)); s \\ Charles R Greathouse IV, Oct 19 2017

(define (A008479 n) (if (not (zero? (A008683 n))) 1 (+ 1 (A008479 (A285328 n))))) ;; Antti Karttunen, Apr 17 2017

a(n) = Sum_{k=1..n} (floor(n^k/k)-floor((n^k-1)/k))*(floor(k^n/n)-floor((k^n-1)/n)). - Anthony Browne, May 20 2016
If A008683(n) <> 0 [when n is squarefree, A005117], a(n) = 1, otherwise a(n) = 1+a(A285328(n)). - Antti Karttunen, Apr 17 2017
a(n) <= A010846(n), with equality if and only if n = 1. - Amiram Eldar, May 25 2025
a(m^(k+1)) = A010846(m^k) when m is squarefree. - Flávio V. Fernandes, Aug 20 2025

A285328 a(n) = 1 if n is squarefree (A005117), otherwise a(n) = Max {m < n | same prime factors as n, ignoring multiplicity}.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 4, 3, 1, 1, 6, 1, 1, 1, 8, 1, 12, 1, 10, 1, 1, 1, 18, 5, 1, 9, 14, 1, 1, 1, 16, 1, 1, 1, 24, 1, 1, 1, 20, 1, 1, 1, 22, 15, 1, 1, 36, 7, 40, 1, 26, 1, 48, 1, 28, 1, 1, 1, 30, 1, 1, 21, 32, 1, 1, 1, 34, 1, 1, 1, 54, 1, 1, 45, 38, 1, 1, 1, 50, 27, 1, 1, 42, 1, 1, 1, 44, 1, 60, 1, 46, 1, 1, 1, 72, 1, 56, 33, 80, 1, 1, 1, 52, 1, 1, 1, 96

Offset: 1

Antti Karttunen, Apr 17 2017

nonn

			From _Michael De Vlieger_, Dec 31 2018: (Start)
a(1) = 1 since 1 is squarefree.
a(2) = 1 since 2 is squarefree.
a(4) = 2 since 4 is not squarefree and 2 is the largest number less than 4 that has all the distinct prime divisors that 4 has.
a(6) = 1 since 6 is squarefree.
a(12) = 6 since 12 is not squarefree and 6 is the largest number less than 12 that has all the distinct prime divisors that 12 has. (6 is also the squarefree root of 12).
a(16) = 8 since 16 is not squarefree and 8 is the largest number less than 16 that has all the distinct prime divisors that 16 has.
a(18) = 12 since 18 is not squarefree and 12 is the largest number less than 18 that has all the distinct prime divisors that 18 has.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..10000

A left inverse of A065642.
Cf. A005117, A007947, A008479, A008683, A284571, A285111, A285331, A285329.
Cf. also A079277.

Table[With[{r = DivisorSum[n, EulerPhi[#] Abs@ MoebiusMu[#] &]}, If[MoebiusMu@ n != 0, 1, SelectFirst[Range[n - 2, 2, -1], DivisorSum[#, EulerPhi[#] Abs@ MoebiusMu[#] &] == r &]]], {n, 108}] (* Michael De Vlieger, Dec 31 2018 *)

A007947(n) = factorback(factorint(n)[, 1]); \\ From Andrew Lelechenko, May 09 2014
A285328(n) = { my(r=A007947(n)); if(core(n)==n,1,n = n-r; while(A007947(n) <> r, n = n-r); n); }; \\ After Python-code below - Antti Karttunen, Apr 17 2017
A285328(n) = { my(r); if((n > 1 && !bitand(n,(n-1))),(n/2), r=A007947(n); if(r==n,1,n = n-r; while(A007947(n) <> r, n = n-r); n)); }; \\ Version optimized for powers of 2.

from operator import mul
from sympy import primefactors
from sympy.ntheory.factor_ import core
def a007947(n): return 1 if n<2 else reduce(mul, primefactors(n))
def a(n):
    if core(n) == n: return 1
    r = a007947(n)
    k = n - r
    while k>0:
        if a007947(k) == r: return k
        else: k -= r
print([a(n) for n in range(1, 121)]) # Indranil Ghosh and Antti Karttunen, Apr 17 2017

(definec (A285328 n) (if (not (zero? (A008683 n))) 1 (let ((k (A007947 n))) (let loop ((n (- n k))) (if (= (A007947 n) k) n (loop (- n k)))))))

If A008683(n) <> 0, a(n) = 1, otherwise a(n) = the largest number k < n for which A007947(k) = A007947(n).
Other identities. For all n >= 1:
a(A065642(n)) = n.

A284311 Array T(n,k) read by antidiagonals (downward): T(1,k) = A005117(k+1) (squarefree numbers > 1); for n > 1, columns are nonsquarefree numbers (in ascending order) with exactly the same prime factors as T(1,k).

Original entry on oeis.org

2, 3, 4, 5, 9, 8, 6, 25, 27, 16, 7, 12, 125, 81, 32, 10, 49, 18, 625, 243, 64, 11, 20, 343, 24, 3125, 729, 128, 13, 121, 40, 2401, 36, 15625, 2187, 256, 14, 169, 1331, 50, 16807, 48, 78125, 6561, 512, 15, 28, 2197, 14641, 80, 117649, 54, 390625, 19683, 1024

Offset: 1

Bob Selcoe, Mar 24 2017

A permutation of the natural numbers > 1.

T(1,k)= A005117(m) with m > 1; terms in column k = T(1,k) * A162306(T(1,k)) only not bounded by T(1,k). Let T(1,k) = b. Terms in column k are multiples of b and numbers c such that c | b^e with e >= 0. Alternatively, terms in column k are multiples bc with c those numbers whose prime divisors p also divide b. - Michael De Vlieger, Mar 25 2017

			Array starts:
    2    3     5  6      7  10       11        13  14  15
    4    9    25 12     49  20      121       169  28  45
    8   27   125 18    343  40     1331      2197  56  75
   16   81   625 24   2401  50    14641    371293  98 135
   32  243  3125 36  16807  80   161051   4826809 112 225
   64  729 15625 48 117649 100  1771561  62748517 196 375
  128 2187 78125 54 823543 160 19487171 815730721 224 405
Column 6 is: T(1,6) = 2*5; T(2,6) = 2^2*5; T(3,6) = 2^3*5; T(4,6) = 2*5^2; T(5,6) = 2^4*5, etc.

Alois P. Heinz, Antidiagonals n = 1..141, flattened

Cf. A005117 (squarefree numbers), A033845 (column 4), columns 1,2,3,5 are powers of primes, A033846 (column 6), A033847 (column 9), A033849 (column 10).
The columns that are powers of primes have indices A071403(n) - 1. - Michel Marcus, Mar 24 2017
See also A007947; the k-th column of the array corresponds to the numbers with radical A005117(k+1). - Rémy Sigrist, Mar 24 2017
Cf. A284457 (this sequence read by antidiagonals upwards), A285321 (a similar array, but columns come in different order).
Cf. A065642.
Cf. A008479 (index of the row where n is located), A285329 (of the column).

f[n_, k_: 1] := Block[{c = 0, sgn = Sign[k], sf}, sf = n + sgn; While[c < Abs[k], While[! SquareFreeQ@ sf, If[sgn < 0, sf--, sf++]]; If[sgn < 0, sf--, sf++]; c++]; sf + If[sgn < 0, 1, -1]] (* after Robert G. Wilson v at A005117 *); T[n_, k_] := T[n, k] = Which[And[n == 1, k == 1], 2, k == 1, f@ T[n - 1, k], PrimeQ@ T[n, 1], T[n, 1]^k, True, Module[{j = T[n, k - 1]/T[n, 1] + 1}, While[PowerMod[T[n, 1], j, j] != 0, j++]; j T[n, 1]]]; Table[T[n - k + 1, k], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, Mar 25 2017 *)

(define (A284311 n) (A284311bi  (A002260 n) (A004736 n)))
(define (A284311bi row col) (if (= 1 row) (A005117 (+ 1 col)) (A065642 (A284311bi (- row 1) col))))
;; Antti Karttunen, Apr 17 2017

From Antti Karttunen, Apr 17 2017: (Start)
A(1,k) = A005117(1+k), A(n,k) = A065642(A(n-1,k)).
A(A008479(n), A285329(n)) = n for all n >= 2.
(End)

A284457 Square array whose rows list numbers with the same squarefree kernel (A007947): Transpose of A284311.

Original entry on oeis.org

2, 4, 3, 8, 9, 5, 16, 27, 25, 6, 32, 81, 125, 12, 7, 64, 243, 625, 18, 49, 10, 128, 729, 3125, 24, 343, 20, 11, 256, 2187, 15625, 36, 2401, 40, 121, 13, 512, 6561, 78125, 48, 16807, 50, 1331, 169, 14, 1024, 19683, 390625, 54, 117649, 80, 14641, 2197, 28, 15

Offset: 1

Bob Selcoe, Mar 27 2017

The first column contains the squarefree numbers A005117; each row lists all numbers having the same prime divisors. If T[m,1] is prime then the row contains the powers of that prime. Yields A182944 if only these rows with prime powers (A000961) are kept. - M. F. Hasler, Mar 27 2017

See A284311 for further details.

			Array starts:
    2    4     8     16      32      64      128
    3    9    27     81     243     729     2187
    5   25   125    625    3125   15625    78125
    6   12    18     24      36      48       54
    7   49   343   2401   16807  117649   823543
   10   20    40     50      80     100      160
   ...
Row 6 is: T[1,6] = 2*5; T[2,6] = 2^2*5; T[3,6] = 2^3*5; T[4,6] = 2*5^2; T[5,6] = 2^4*5, etc.

Alois P. Heinz, Antidiagonals n = 1..141, flattened

Cf. A284311, A005117, A007947, A065642, A182944.

Cf. A008479 (index of the column where n is located), A285329 (of the row).

f[n_, k_: 1] := Block[{c = 0, sgn = Sign[k], sf}, sf = n + sgn; While[c < Abs@ k, While[! SquareFreeQ@ sf, If[sgn < 0, sf--, sf++]]; If[sgn < 0, sf--, sf++]; c++]; sf + If[sgn < 0, 1, -1]] (* after Robert G. Wilson v at A005117 *); T[n_, k_] := T[n, k] = Which[And[n == 1, k == 1], 2, k == 1, f@ T[n - 1, k], PrimeQ@ T[n, 1], T[n, 1]^k, True, Module[{j = T[n, k - 1]/T[n, 1] + 1}, While[PowerMod[T[n, 1], j, j] != 0, j++]; j T[n, 1]]]; Table[T[n - k + 1, k], {n, 10}, {k, n, 1, -1}] // Flatten

A284457(m,n)={for(a=2,m^2+1,(core(a)!=a||m--)&&next;m=factor(a)[,1]; for(k=1,9e9,factor(k*a)[,1]==m&&!n--&&return(k*a)))} \\ M. F. Hasler, Mar 27 2017

(define (A284457 n) (A284311bi (A004736 n) (A002260 n))) ;; For A284311bi, see A284311. - Antti Karttunen, Apr 17 2017

From Antti Karttunen, Apr 17 2017: (Start)
A(n,1) = A005117(1+n), A(n,k) = A065642(A(n,k-1)). [A "dispersion" of A065642.]
A(A285329(n), A008479(n)) = n for all n >= 2.(End)

Edited by M. F. Hasler, Mar 27 2017

A322590 Lexicographically earliest such positive sequence a that a(i) = a(j) => A007947(i) = A007947(j) for all i, j.

Original entry on oeis.org

1, 2, 3, 2, 4, 5, 6, 2, 3, 7, 8, 5, 9, 10, 11, 2, 12, 5, 13, 7, 14, 15, 16, 5, 4, 17, 3, 10, 18, 19, 20, 2, 21, 22, 23, 5, 24, 25, 26, 7, 27, 28, 29, 15, 11, 30, 31, 5, 6, 7, 32, 17, 33, 5, 34, 10, 35, 36, 37, 19, 38, 39, 14, 2, 40, 41, 42, 22, 43, 44, 45, 5, 46, 47, 11, 25, 48, 49, 50, 7, 3, 51, 52, 28, 53, 54, 55, 15, 56, 19, 57, 30, 58, 59, 60, 5, 61, 10, 21, 7, 62, 63, 64, 17

Offset: 1

Antti Karttunen, Dec 17 2018

nonn

Restricted growth sequence transform of A007947.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A007947, A008479 (ordinal transform).

One more than A285329.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A007947(n) = factorback(factorint(n)[, 1]);
v322590 = rgs_transform(vector(up_to, n, A007947(n)));
A322590(n) = v322590[n];

a(n) = 1 + A285329(n).

cp's OEIS Frontend

A087207 A binary representation of the primes that divide a number, shown in decimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Scheme

Formula

Extensions

A008479 Number of numbers <= n with same prime factors as n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Scheme

Formula

A285328 a(n) = 1 if n is squarefree (A005117), otherwise a(n) = Max {m < n | same prime factors as n, ignoring multiplicity}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula

A284311 Array T(n,k) read by antidiagonals (downward): T(1,k) = A005117(k+1) (squarefree numbers > 1); for n > 1, columns are nonsquarefree numbers (in ascending order) with exactly the same prime factors as T(1,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A284457 Square array whose rows list numbers with the same squarefree kernel (A007947): Transpose of A284311.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

Extensions

A322590 Lexicographically earliest such positive sequence a that a(i) = a(j) => A007947(i) = A007947(j) for all i, j.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula