A087436 -id:A087436 - cp's OEIS frontend

A000244 Powers of 3: a(n) = 3^n.

1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987

Offset: 0

N. J. A. Sloane

Same as Pisot sequences E(1, 3), L(1, 3), P(1, 3), T(1, 3). Essentially same as Pisot sequences E(3, 9), L(3, 9), P(3, 9), T(3, 9). See A008776 for definitions of Pisot sequences.
Number of (s(0), s(1), ..., s(2n+2)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2n + 2, s(0) = 1, s(2n+2) = 3. - Herbert Kociemba, Jun 10 2004
a(1) = 1, a(n+1) is the least number such that there are a(n) even numbers between a(n) and a(n+1). Generalization for the sequence of powers of k: 1, k, k^2, k^3, k^4, ... There are a(n) multiples of k-1 between a(n) and a(n+1). - Amarnath Murthy, Nov 28 2004
a(n) = sum of (n+1)-th row in Triangle A105728. - Reinhard Zumkeller, Apr 18 2005
With p(n) being the number of integer partitions of n, p(i) being the number of parts of the i-th partition of n, d(i) being the number of different parts of the i-th partition of n, m(i, j) being the multiplicity of the j-th part of the i-th partition of n, Sum_{i = 1..p(n)} being the sum over i and Product_{j = 1..d(i)} being the product over j, one has: a(n) = Sum_{i = 1..p(n)} (p(i)!/(Product_{j = 1..d(i)} m(i, j)!))*2^(p(i) - 1). - Thomas Wieder, May 18 2005
For any k > 1 in the sequence, k is the first prime power appearing in the prime decomposition of repunit R_k, i.e., of A002275(k). - Lekraj Beedassy, Apr 24 2006
a(n-1) is the number of compositions of compositions. In general, (k+1)^(n-1) is the number of k-levels nested compositions (e.g., 4^(n-1) is the number of compositions of compositions of compositions, etc.). Each of the n - 1 spaces between elements can be a break for one of the k levels, or not a break at all. - Franklin T. Adams-Watters, Dec 06 2006
Let S be a binary relation on the power set P(A) of a set A having n = |A| elements such that for every element x, y of P(A), xSy if x is a subset of y. Then a(n) = |S|. - Ross La Haye, Dec 22 2006
From Manfred Boergens, Mar 28 2023: (Start)
With regard to the comment by Ross La Haye:
Cf. A001047 if either nonempty subsets are considered or x is a proper subset of y.
Cf. a(n+1) in A028243 if nonempty subsets are considered and x is a proper subset of y. (End)
If X_1, X_2, ..., X_n is a partition of the set {1, 2, ..., 2*n} into blocks of size 2 then, for n >= 1, a(n) is equal to the number of functions f : {1, 2, ..., 2*n} -> {1, 2} such that for fixed y_1, y_2, ..., y_n in {1, 2} we have f(X_i) <> {y_i}, (i = 1, 2, ..., n). - Milan Janjic, May 24 2007
This is a general comment on all sequences of the form a(n) = [(2^k)-1]^n for all positive integers k. Example 1.1.16 of Stanley's "Enumerative Combinatorics" offers a slightly different version. a(n) in the number of functions f:[n] into P([k]) - {}. a(n) is also the number of functions f:[k] into P([n]) such that the generalized intersection of f(i) for all i in [k] is the empty set. Where [n] = {1, 2, ..., n}, P([n]) is the power set of [n] and {} is the empty set. - Geoffrey Critzer, Feb 28 2009
a(n) = A064614(A000079(n)) and A064614(m)A000079(n). - Reinhard Zumkeller, Feb 08 2010
3^(n+1) = (1, 2, 2, 2, ...) dot (1, 1, 3, 9, ..., 3^n); e.g., 3^3 = 27 = (1, 2, 2, 2) dot (1, 1, 3, 9) = (1 + 2 + 6 + 18). - Gary W. Adamson, May 17 2010
a(n) is the number of generalized compositions of n when there are 3*2^i different types of i, (i = 1, 2, ...). - Milan Janjic, Sep 24 2010
For n >= 1, a(n-1) is the number of generalized compositions of n when there are 2^(i-1) different types of i, (i = 1, 2, ...). - Milan Janjic, Sep 24 2010
The sequence in question ("Powers of 3") also describes the number of moves of the k-th disk solving the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Tower of Hanoi puzzle (cf. A183111 - A183125).
a(n) is the number of Stern polynomials of degree n. See A057526. - T. D. Noe, Mar 01 2011
Positions of records in the number of odd prime factors, A087436. - Juri-Stepan Gerasimov, Mar 17 2011
Sum of coefficients of the expansion of (1+x+x^2)^n. - Adi Dani, Jun 21 2011
a(n) is the number of compositions of n elements among {0, 1, 2}; e.g., a(2) = 9 since there are the 9 compositions 0 + 0, 0 + 1, 1 + 0, 0 + 2, 1 + 1, 2 + 0, 1 + 2, 2 + 1, and 2 + 2. [From Adi Dani, Jun 21 2011; modified by editors.]
Except the first two terms, these are odd numbers n such that no x with 2 <= x <= n - 2 satisfy x^(n-1) == 1 (mod n). - Arkadiusz Wesolowski, Jul 03 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 1, a(n) equals the number of 3-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Explanation from David Applegate, Feb 20 2017: (Start)
Since the preceding comment appears in a large number of sequences, it might be worth adding a proof.
The number of compositions of n into exactly k parts is binomial(n-1,k-1).
For a p-colored composition of n such that no adjacent parts have the same color, there are exactly p choices for the color of the first part, and p-1 choices for the color of each additional part (any color other than the color of the previous one). So, for a partition into k parts, there are p (p-1)^(k-1) valid colorings.
Thus the number of p-colored compositions of n into exactly k parts such that no adjacent parts have the same color is binomial(n-1,k-1) p (p-1)^(k-1).
The total number of p-colored compositions of n such that no adjacent parts have the same color is then
Sum_{k=1..n} binomial(n-1,k-1) * p * (p-1)^(k-1) = p^n.
To see this, note that the binomial expansion of ((p - 1) + 1)^(n - 1) = Sum_{k = 0..n - 1} binomial(n - 1, k) (p - 1)^k 1^(n - 1 - k) = Sum_{k = 1..n} binomial(n - 1, k - 1) (p - 1)^(k - 1).
(End)
Also, first and least element of the matrix [1, sqrt(2); sqrt(2), 2]^(n+1). - M. F. Hasler, Nov 25 2011
One-half of the row sums of the triangular version of A035002. - J. M. Bergot, Jun 10 2013
Form an array with m(0,n) = m(n,0) = 2^n; m(i,j) equals the sum of the terms to the left of m(i,j) and the sum of the terms above m(i,j), which is m(i,j) = Sum_{k=0..j-1} m(i,k) + Sum_{k=0..i-1} m(k,j). The sum of the terms in antidiagonal(n+1) = 4*a(n). - J. M. Bergot, Jul 10 2013
a(n) = A007051(n+1) - A007051(n), and A007051 are the antidiagonal sums of an array defined by m(0,k) = 1 and m(n,k) = Sum_{c = 0..k - 1} m(n, c) + Sum_{r = 0..n - 1} m(r, k), which is the sum of the terms to left of m(n, k) plus those above m(n, k). m(1, k) = A000079(k); m(2, k) = A045623(k + 1); m(k + 1, k) = A084771(k). - J. M. Bergot, Jul 16 2013
Define an array to have m(0,k) = 2^k and m(n,k) = Sum_{c = 0..k - 1} m(n, c) + Sum_{r = 0..n - 1} m(r, k), which is the sum of the terms to the left of m(n, k) plus those above m(n, k). Row n = 0 of the array comprises A000079, column k = 0 comprises A011782, row n = 1 comprises A001792. Antidiagonal sums of the array are a(n): 1 = 3^0, 1 + 2 = 3^1, 2 + 3 + 4 = 3^2, 4 + 7 + 8 + 8 = 3^3. - J. M. Bergot, Aug 02 2013
The sequence with interspersed zeros and o.g.f. x/(1 - 3*x^2), A(2*k) = 0, A(2*k + 1) = 3^k = a(k), k >= 0, can be called hexagon numbers. This is because the algebraic number rho(6) = 2*cos(Pi/6) = sqrt(3) of degree 2, with minimal polynomial C(6, x) = x^2 - 3 (see A187360, n = 6), is the length ratio of the smaller diagonal and the side in the hexagon. Hence rho(6)^n = A(n-1)*1 + A(n)*rho(6), in the power basis of the quadratic number field Q(rho(6)). One needs also A(-1) = 1. See also a Dec 02 2010 comment and the P. Steinbach reference given in A049310. - Wolfdieter Lang, Oct 02 2013
Numbers k such that sigma(3k) = 3k + sigma(k). - Jahangeer Kholdi, Nov 23 2013
All powers of 3 are perfect totient numbers (A082897), since phi(3^n) = 2 * 3^(n - 1) for n > 0, and thus Sum_{i = 0..n} phi(3^i) = 3^n. - Alonso del Arte, Apr 20 2014
The least number k > 0 such that 3^k ends in n consecutive decreasing digits is a 3-term sequence given by {1, 13, 93}. The consecutive increasing digits are {3, 23, 123}. There are 100 different 3-digit endings for 3^k. There are no k-values such that 3^k ends in '012', '234', '345', '456', '567', '678', or '789'. The k-values for which 3^k ends in '123' are given by 93 mod 100. For k = 93 + 100*x, the digit immediately before the run of '123' is {9, 5, 1, 7, 3, 9, 5, 1, 3, 7, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus we see the digit before '123' will never be a 0. So there are no further terms. - Derek Orr, Jul 03 2014
All elements of A^n where A = (1, 1, 1; 1, 1, 1; 1, 1, 1). - David Neil McGrath, Jul 23 2014
Counts all walks of length n (open or closed) on the vertices of a triangle containing a loop at each vertex starting from any given vertex. - David Neil McGrath, Oct 03 2014
a(n) counts walks (closed) on the graph G(1-vertex;1-loop,1-loop,1-loop). - David Neil McGrath, Dec 11 2014
2*a(n-2) counts all permutations of a solitary closed walk of length (n) from the vertex of a triangle that contains 2 loops on each of the remaining vertices. In addition, C(m,k)=2*(2^m)*B(m+k-2,m) counts permutations of walks that contain (m) loops and (k) arcs. - David Neil McGrath, Dec 11 2014
a(n) is the sum of the coefficients of the n-th layer of Pascal's pyramid (a.k.a., Pascal's tetrahedron - see A046816). - Bob Selcoe, Apr 02 2016
Numbers n such that the trinomial x^(2*n) + x^n + 1 is irreducible over GF(2). Of these only the trinomial for n=1 is primitive. - Joerg Arndt, May 16 2016
Satisfies Benford's law [Berger-Hill, 2011]. - N. J. A. Sloane, Feb 08 2017
a(n-1) is also the number of compositions of n if the parts can be runs of any length from 1 to n, and can contain any integers from 1 to n. - Gregory L. Simay, May 26 2017
Also the number of independent vertex sets and vertex covers in the n-ladder rung graph n P_2. - Eric W. Weisstein, Sep 21 2017
Also the number of (not necessarily maximal) cliques in the n-cocktail party graph. - Eric W. Weisstein, Nov 29 2017
a(n-1) is the number of 2-compositions of n; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 15 2020
a(n) is the number of faces of any dimension (vertices, edges, square faces, etc.) of the n-dimensional hypercube. For example, the 0-dimensional hypercube is a point, and its only face is itself. The 1-dimensional hypercube is a line, which has two vertices and an edge. The 2-dimensional hypercube is a square, which has four vertices, four edges, and a square face. - Kevin Long, Mar 14 2023
Number of pairs (A,B) of subsets of M={1,2,...,n} with union(A,B)=M. For nonempty subsets cf. A058481. - Manfred Boergens, Mar 28 2023
From Jianing Song, Sep 27 2023: (Start)
a(n) is the number of disjunctive clauses of n variables up to equivalence. A disjunctive clause is a propositional formula of the form l_1 OR ... OR l_m, where l_1, ..., l_m are distinct elements in {x_1, ..., x_n, NOT x_1, ..., NOT x_n} for n variables x_1, ... x_n, and no x_i and NOT x_i appear at the same time. For each 1 <= i <= n, we can have neither of x_i or NOT x_i, only x_i or only NOT x_i appearing in a disjunctive clause, so the number of such clauses is 3^n. Viewing the propositional formulas of n variables as functions {0,1}^n -> {0,1}, a disjunctive clause corresponds to a function f such that the inverse image of 0 is of the form A_1 X ... X A_n, where A_i is nonempty for all 1 <= i <= n. Since each A_i has 3 choices ({0}, {1} or {0,1}), we also find that the number of disjunctive clauses of n variables is 3^n.
Equivalently, a(n) is the number of conjunctive clauses of n variables. (End)
The finite subsequence a(2), a(3), a(4), a(5) = 9, 27, 81, 243 is one of only two geometric sequences that can be formed with all interior angles (all integer, in degrees) of a simple polygon. The other sequence is a subsequence of A007283 (see comment there). - Felix Huber, Feb 15 2024

			G.f. = 1 + 3*x + 9*x^2 + 27*x^3 + 81*x^4 + 243*x^5 + 729*x^6 + 2187*x^7 + ...

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
T. Banchoff, Counting the Faces of Higher-Dimensional Cubes, Beyond the Third Dimension: Geometry, computer graphics and higher dimensions, Scientific American Library, 1996.
Arno Berger and Theodore P. Hill, Benford's law strikes back: no simple explanation in sight for mathematical gem, The Mathematical Intelligencer 33.1 (2011): 85-91.
A. Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Ph. Flajolet, Mar 28 2013.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 7
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 268
Milan Janjic, Enumerative Formulae for Some Functions on Finite Sets
Tanya Khovanova, Recursive Sequences
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Eric Weisstein's World of Mathematics, Clique.
Eric Weisstein's World of Mathematics, Cocktail Party Graph.
Eric Weisstein's World of Mathematics, Hanoi Graph.
Eric Weisstein's World of Mathematics, Independent Vertex Set.
Eric Weisstein's World of Mathematics, Ladder Rung Graph.
Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
Eric Weisstein's World of Mathematics, Vertex Cover.
Doron Zeilberger, The Amazing 3^n Theorem and its even more Amazing Proof [Discovered by Xavier G. Viennot and his École Bordelaise gang], arXiv:1208.2258, 2012.
Index entries for "core" sequences
Index entries for related partition-counting sequences
Index entries for linear recurrences with constant coefficients, signature (3).
Index entries for sequences related to Benford's law

Cf. A008776 (2*a(n), and first differences).
a(n) = A092477(n, 2) for n > 0.
a(n) = A159991(n) / A009964(n).
Cf. A100772, A035002. Row sums of A125076 and A153279.
a(n) = A217764(0, n).
Cf. A046816, A006521, A014945, A275414 (multisets).
The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).
Cf. A001047, A028243, A058481.

a000244 = (3 ^)  -- Reinhard Zumkeller, Nov 14 2011
a000244_list = iterate (* 3) 1  -- Reinhard Zumkeller, Apr 04 2012

[ 3^n : n in [0..30] ]; // Wesley Ivan Hurt, Jul 04 2014

A000244 := n->3^n; [ seq(3^n, n=0..50) ];
A000244:=-1/(-1+3*z); # Simon Plouffe in his 1992 dissertation.

Table[3^n, {n, 0, 30}] (* Stefan Steinerberger, Apr 01 2006 *)
3^Range[0, 30] (* Wesley Ivan Hurt, Jul 04 2014 *)
LinearRecurrence[{3}, {1}, 20] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 3 x), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
NestList[3#&,1,30] (* Harvey P. Dale, Feb 20 2020 *)

makelist(3^n, n, 0, 30); /* Martin Ettl, Nov 05 2012 */

A000244(n) = 3^n \\ Michael B. Porter, Nov 03 2009

def A000244(n): return 3**n # Chai Wah Wu, Nov 10 2022

val powersOf3: LazyList[BigInt] = LazyList.iterate(1: BigInt)(_ * 3)
(0 to 26).map(powersOf3()) // _Alonso del Arte, May 03 2020

a(n) = 3^n.
a(0) = 1; a(n) = 3*a(n-1).
G.f.: 1/(1-3*x).
E.g.f.: exp(3*x).
a(n) = n!*Sum_{i + j + k = n, i, j, k >= 0} 1/(i!*j!*k!). - Benoit Cloitre, Nov 01 2002
a(n) = Sum_{k = 0..n} 2^k*binomial(n, k), binomial transform of A000079.
a(n) = A090888(n, 2). - Ross La Haye, Sep 21 2004
a(n) = 2^(2n) - A005061(n). - Ross La Haye, Sep 10 2005
a(n) = A112626(n, 0). - Ross La Haye, Jan 11 2006
Hankel transform of A007854. - Philippe Deléham, Nov 26 2006
a(n) = 2*StirlingS2(n+1,3) + StirlingS2(n+2,2) = 2*(StirlingS2(n+1,3) + StirlingS2(n+1,2)) + 1. - Ross La Haye, Jun 26 2008
a(n) = 2*StirlingS2(n+1, 3) + StirlingS2(n+2, 2) = 2*(StirlingS2(n+1, 3) + StirlingS2(n+1, 2)) + 1. - Ross La Haye, Jun 09 2008
Sum_{n >= 0} 1/a(n) = 3/2. - Gary W. Adamson, Aug 29 2008
If p(i) = Fibonacci(2i-2) and if A is the Hessenberg matrix of order n defined by A(i, j) = p(j-i+1), (i <= j), A(i, j) = -1, (i = j+1), and A(i, j) = 0 otherwise, then, for n >= 1, a(n-1) = det A. - Milan Janjic, May 08 2010
G.f. A(x) = M(x)/(1-M(x))^2, M(x) - o.g.f for Motzkin numbers (A001006). - Vladimir Kruchinin, Aug 18 2010
a(n) = A133494(n+1). - Arkadiusz Wesolowski, Jul 27 2011
2/3 + 3/3^2 + 2/3^3 + 3/3^4 + 2/3^5 + ... = 9/8. [Jolley, Summation of Series, Dover, 1961]
a(n) = Sum_{k=0..n} A207543(n,k)*4^(n-k). - Philippe Deléham, Feb 25 2012
a(n) = Sum_{k=0..n} A125185(n,k). - Philippe Deléham, Feb 26 2012
Sum_{n > 0} Mobius(n)/a(n) = 0.181995386702633887827... (see A238271). - Alonso del Arte, Aug 09 2012. See also the sodium 3s orbital energy in table V of J. Chem. Phys. 53 (1970) 348.
a(n) = (tan(Pi/3))^(2*n). - Bernard Schott, May 06 2022
a(n-1) = binomial(2*n-1, n) + Sum_{k >= 1} binomial(2*n, n+3*k)*(-1)^k. - Greg Dresden, Oct 14 2022
G.f.: Sum_{k >= 0} x^k/(1-2*x)^(k+1). - Kevin Long, Mar 14 2023

A093641 Numbers of form 2^i * prime(j), i>=0, j>0, together with 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 48, 52, 53, 56, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 76, 79, 80, 82, 83, 86, 88, 89, 92, 94, 96, 97, 101, 103, 104, 106, 107, 109, 112

Offset: 1

Reinhard Zumkeller, Apr 07 2004

a(n) is either 1, prime, or of form 2a(m), m

1 and Heinz numbers of hook integer partitions. The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k). A hook is a partition of the form (n,1,1,...,1). - Gus Wiseman, Sep 15 2018

Numbers whose odd part is noncomposite. - Peter Munn, Aug 06 2020

			55 is not a member, as 5*11 is not of the form 2^i * prime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

A093640(a(n)) = A000005(a(n)); A000040 and A000079 are subsequences.
A105440 is a subsequence, see also A105442. - Reinhard Zumkeller, Apr 09 2005
Cf. A078822, A007088.
Complement of A105441; A001221(a(n))<=2; A005087(a(n))<=1; A087436(a(n))<=1.
See also A105442.
Union of A038550 and A000079, see also A008578.
Cf. A082733, A153452, A296188, A296561, A300121, A304438, A305940, A317554.
Cf. A000265 (odd part), A008578 (noncomposite).

a093641 n = a093641_list !! (n-1)
a093641_list = filter ((<= 2) . a001227) [1..]
-- Reinhard Zumkeller, May 01 2012

hookQ[n_]:=MatchQ[DeleteCases[FactorInteger[n],{2,}],{}|{{,1}}];
Select[Range[100],hookQ] (* Gus Wiseman, Sep 15 2018 *)

upTo(lim)=my(v=List([1])); for(e=0, log(lim)\log(2), forprime(p=2, lim>>e, listput(v,p<Charles R Greathouse IV, Aug 21 2011

isok(m) = my(k=m/2^valuation(m,2)); (k == 1) || isprime(k); \\ Michel Marcus, Mar 16 2023

from sympy import primepi
def A093641(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n-1+x-sum(primepi(x>>i) for i in range(x.bit_length()))
    return bisection(f,n,n) # Chai Wah Wu, Feb 02 2025

A001227(a(n)) <= 2. - Reinhard Zumkeller, May 01 2012

Number A(x) of a(n) not exceeding x equals 1 + pi(x) + pi(x/2) + pi(x/4) + ..., where pi(x) is the number of primes <= x. If x goes to infinity, A(x)~2*x/log(x) and a(n)~n*log(n)/2 (n-->infinity). - Vladimir Shevelev, Feb 06 2014

A329697 a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k-(k/p), where p is the largest prime factor of k.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 2, 0, 1, 2, 3, 1, 3, 2, 3, 1, 2, 2, 3, 2, 3, 2, 3, 0, 3, 1, 3, 2, 3, 3, 3, 1, 2, 3, 4, 2, 3, 3, 4, 1, 4, 2, 2, 2, 3, 3, 3, 2, 4, 3, 4, 2, 3, 3, 4, 0, 3, 3, 4, 1, 4, 3, 4, 2, 3, 3, 3, 3, 4, 3, 4, 1, 4, 2, 3, 3, 2, 4, 4, 2, 3, 3, 4, 3, 4, 4, 4, 1, 2, 4, 4, 2

Offset: 1

Ali Sada and Robert G. Wilson v, Feb 28 2020

From Antti Karttunen, Apr 07 2020: (Start)
Also the least number of iterations of nondeterministic map k -> k-(k/p) needed to reach a power of 2, when any prime factor p of k can be used. The minimal length path to the nearest power of 2 (= 2^A064415(n)) is realized whenever one uses any of the A005087(k) distinct odd prime factors of the current k, at any step of the process. For example, this could be done by iterating with the map k -> k-(k/A078701(k)), i.e., by using the least odd prime factor of k (instead of the largest prime).
Proof: Viewing the prime factorization of changing k as a multiset ("bag") of primes, we see that liquefying any odd prime p with step p -> (p-1) brings at least one more 2 to the bag, while applying p -> (p-1) to any 2 just removes it from the bag, but gives nothing back. Thus the largest (and thus also the nearest) power of 2 is reached by eliminating - step by step - all odd primes from the bag, but none of 2's, and it doesn't matter in which order this is done.
The above implies also that the sequence is totally additive, which also follows because both A064097 and A064415 are. That A064097(n) = A329697(n) + A054725(n) for all n > 1 can be also seen by comparing the initial conditions and the recursion formulas of these three sequences.
For any n, A333787(n) is either the nearest power of 2 reached (= 2^A064415(n)), or occurs on some of the paths from n to there.
(End)
A003401 gives the numbers k where a(k) = A005087(k). See also A336477. - Antti Karttunen, Mar 16 2021

			The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
From _Antti Karttunen_, Apr 07 2020: (Start)
Considering all possible paths from 15 to 1 nondeterministic map k -> k-(k/p), where p can be any prime factor of k, we obtain the following graph:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1.
It can be seen that there's also alternative route to 8 via 10 (with 10 = 15-(15/3), where 3 is not the largest prime factor of 15), but it's not any shorter than the route via 12.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..65537
Michael De Vlieger, Annotated fan style binary tree labeling the index n, with a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value in a(n) for n = 1..16383.

Cf. A000265, A003401, A005087, A052126, A053575, A054725, A064097, A064415, A078701, A087436, A147545, A171462, A209229, A333123, A333787, A333790, A334107, A334109, A335875, A334204, A335880, A335881, A336396, A336466, A336469 [= a(phi(n))], A336928 [= a(sigma(n))], A336470, A336477, A339970.
Cf. A000079, A334101, A334102, A334103, A334104, A334105, A334106 for positions of 0 .. 6 in this sequence, and also array A334100.
Cf. A334099 (a right inverse, positions of the first occurrence of each n).
Cf. A334091 (first differences), A335429 (partial sums).
Cf. also A331410 (analogous sequence when using the map k -> k + k/p), A334861, A335877 (their sums and differences), see also A335878 and A335884, A335885.

a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, Apr 07 2020

up_to = 2^24;
A329697list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2, up_to, v[n] = if(!bitand(n,n-1),0,1+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~)))); (v); };
v329697 = A329697list(up_to);
A329697(n) = v329697[n]; \\ Antti Karttunen, Apr 07 2020

A329697(n) = if(n<=2,0, if(isprime(n), A329697(n-1)+1, my(f=factor(n)); (apply(A329697, f[, 1])~ * f[, 2]))); \\ Antti Karttunen, Apr 19 2020

From Antti Karttunen, Apr 07-19 2020: (Start)
a(1) = a(2) = 0; and for n > 2, a(p) = 1 + a(p-1) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [This is otherwise equal to the definition of A064097, except here we have a different initial condition, with a(2) = 0].
a(2n) = a(A000265(n)) = a(n).
a(p) = 1+a(p-1), for all odd primes p.
If A209229(n) == 1 [when n is a power of 2], a(n) = 0,
  otherwise a(n) = 1 + a(n-A052126(n)) = 1 + a(A171462(n)).
Equivalently, for non-powers of 2, a(n) = 1 + a(n-(n/A078701(n))),
or equivalently, for non-powers of 2, a(n) = 1 + Min a(n - n/p), for p prime and dividing n.
a(n) = A064097(n) - A064415(n), or equally, a(n) = A064097(n) - A054725(n), for n > 1.
a(A019434(n)) = 1, a(A334092(n)) = 2, a(A334093(n)) = 3, etc. for all applicable n.
For all n >= 0, a(A334099(n)) = a(A000244(n)) = a(A000351(n)) = a(A001026(n)) = a(257^n) = a(65537^n) = n.
a(A122111(n)) = A334107(n), a(A225546(n)) = A334109(n).
(End)
From Antti Karttunen, Mar 16 2021: (Start)
a(n) = a(A336466(n)) + A087436(n) = A336396(n) + A087436(n).
a(A053575(n)) = A336469(n) = a(n) - A005087(n).
a(A147545(n)) = A000120(A147545(n)) - 1.
(End)

A331410 a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k + k/p, where p is the largest prime factor of k.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 0, 2, 2, 2, 1, 2, 1, 3, 0, 3, 2, 3, 2, 2, 2, 2, 1, 4, 2, 3, 1, 4, 3, 1, 0, 3, 3, 3, 2, 4, 3, 3, 2, 3, 2, 3, 2, 4, 2, 2, 1, 2, 4, 4, 2, 4, 3, 4, 1, 4, 4, 4, 3, 2, 1, 3, 0, 4, 3, 4, 3, 3, 3, 3, 2, 5, 4, 5, 3, 3, 3, 3, 2, 4, 3, 3, 2, 5, 3, 5, 2, 5, 4, 3, 2, 2, 2, 5, 1, 3, 2, 4, 4, 5, 4, 3, 2, 4

Offset: 1

Ali Sada, Jan 16 2020

nonn

Let f(n) = A000265(n) be the odd part of n. Let p be the largest prime factor of k, and say k = p * m. Suppose that k is not a power of 2, i.e., p > 2, then f(k) = p * f(m). The iteration is k -> k + k/p = p*m + m = (p+1) * m. So, p * f(m) -> f(p+1) * f(m). Since for p > 2, f(p+1) < p, the odd part in each iteration decreases, until it becomes 1, i.e., until we reach a power of 2. - Amiram Eldar, Feb 19 2020
Any odd prime factor of k can be used at any step of the iteration, and the result will be same. Thus, like A329697, this is also fully additive sequence. - Antti Karttunen, Apr 29 2020
If and only if a(n) is equal to A005087(n), then sigma(2n) - sigma(n) is a power of 2. (See A336923, A046528). - Antti Karttunen, Mar 16 2021

			The trajectory of 15 is [15,18,24,32], taking 3 iterations to reach 32. So, a(15) = 3.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Michael De Vlieger, Annotated fan style binary tree of a(n) labeling the index n and applying a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value of a(n) for n = 1..16383.

Cf. A000265, A005087, A006530 (greatest prime factor), A052126, A078701, A087436, A329662 (positions of records and the first occurrences of each n), A334097, A334098, A334108, A334861, A336467, A336921, A336922, A336923 (A046528).
Cf. array A335430, and its rows A335431, A335882, and also A335874.
Cf. also A329697 (analogous sequence when using the map k -> k - k/p), A335878.
Cf. also A330437, A335884, A335885, A336362, A336363 for other similar iterations.

f:=func; g:=func; a:=[]; for n in [1..1000] do k:=n; s:=0; while not g(k) do  s:=s+1; k:=f(k); end while; Append(~a,s); end for; a; // Marius A. Burtea, Jan 19 2020

a[n_] := -1 + Length @ NestWhileList[# + #/FactorInteger[#][[-1, 1]] &, n, # / 2^IntegerExponent[#, 2] != 1 &]; Array[a, 100] (* Amiram Eldar, Jan 16 2020 *)

A331410(n) = if(!bitand(n,n-1),0,1+A331410(n+(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, Apr 29 2020

A331410(n) = { my(k=0); while(bitand(n,n-1), k++; my(f=factor(n)[, 1]); n += (n/f[2-(n%2)])); (k); }; \\ Antti Karttunen, Apr 29 2020

A331410(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+A331410(1+f[k,1])))); }; \\ Antti Karttunen, Apr 30 2020

From Antti Karttunen, Apr 29 2020: (Start)
This is a completely additive sequence: a(2) = 0, a(p) = 1+a(p+1) for odd primes p, a(m*n) = a(m)+a(n), if m,n > 1.
a(2n) = a(A000265(n)) = a(n).
If A209229(n) == 1, a(n) = 0, otherwise a(n) = 1 + a(n+A052126(n)), or equally, 1 + a(n+(n/A078701(n))).
a(n) = A334097(n) - A334098(n).
a(A122111(n)) = A334108(n).
(End)
a(n) = A334861(n) - A329697(n). - Antti Karttunen, May 14 2020
a(n) = a(A336467(n)) + A087436(n) = A336921(n) + A087436(n). - Antti Karttunen, Mar 16 2021

Data section extended up to a(105) by Antti Karttunen, Apr 29 2020

A005087 Number of distinct odd primes dividing n.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 0, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 0, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2

Offset: 1

N. J. A. Sloane

Lei Zhou, Table of n, a(n) for n = 1..10000

Cf. A001221, A077761, A087436.
Positions of zeros: A000079.
Positions of ones: A336101.

a005087 n = a001221 n + n `mod` 2 - 1 -- Reinhard Zumkeller, Feb 28 2014

nn=100; a=Sum[x^p/(1-x^p), {p, Table[Prime[n],{n,2,nn}]}]; Drop[CoefficientList[Series[a, {x,0,nn}],x],1] (* Geoffrey Critzer, Nov 06 2012 *)
Array[PrimeNu[#] - Boole[EvenQ[#]] &, 102] (* Lei Zhou, Dec 03 2012 *)

a(n) = if (n%2, omega(n), omega(n)-1); \\ Michel Marcus, Sep 18 2023

from sympy import primefactors
def A005087(n): return len(primefactors(n))+(n&1)-1 # Chai Wah Wu, Jul 07 2022

def A005087(n) : return len(prime_divisors(n)) + n % 2 - 1
[A005087(n) for n in (1..80)]  # Peter Luschny, Feb 01 2012

Additive with a(p^e) = 0 if p = 2, 1 otherwise.
a(n) = A001221(n) - 1 + n mod 2. - Reinhard Zumkeller, Sep 03 2003
O.g.f.: Sum_{p=odd prime} x^p/(1-x^p). - Geoffrey Critzer, Nov 06 2012
Sum_{k=1..n} a(k) = n * log(log(n)) + c * n + O(n/log(n)), where c = A077761 - 1/2 = -0.238502... . - Amiram Eldar, Sep 28 2023

More terms from Reinhard Zumkeller, Sep 03 2003

Showing 1-10 of 42 results. Next

cp's OEIS Frontend

A336396 a(n) = A329697(n) - A087436(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A336118 a(n) = A335904(n) - A087436(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A336921 a(n) = A331410(n) - A087436(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A342656 a(n) = A087436(A156552(n)); Number of odd prime factors in A156552(n), counted with repetitions.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A336161 Lexicographically earliest infinite sequence such that a(i) = a(j) => A087436(i) = A087436(j) and A335915(i) = A335915(j) for all i, j >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A000244 Powers of 3: a(n) = 3^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Python

Scala

Formula

A093641 Numbers of form 2^i * prime(j), i>=0, j>0, together with 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica