A229153 -id:A229153 - cp's OEIS frontend

A025065 Number of palindromic partitions of n.

1, 1, 2, 2, 4, 4, 7, 7, 12, 12, 19, 19, 30, 30, 45, 45, 67, 67, 97, 97, 139, 139, 195, 195, 272, 272, 373, 373, 508, 508, 684, 684, 915, 915, 1212, 1212, 1597, 1597, 2087, 2087, 2714, 2714, 3506, 3506, 4508, 4508, 5763, 5763, 7338, 7338, 9296, 9296, 11732, 11732, 14742, 14742, 18460, 18460, 23025, 23025, 28629, 28629

Offset: 0

Clark Kimberling

nonn

That is, the number of partitions of n into parts which can be listed in palindromic order.
Alternatively, number of partitions of n into parts from the set {1,2,4,6,8,10,12,...}. - T. D. Noe, Aug 05 2005
Also, partial sums of A035363.
Also number of partitions of n with at most one part occurring an odd number of times. - Reinhard Zumkeller, Dec 18 2013
The first Mathematica program computes terms of A025065; the second computes the k palindromic partitions of user-chosen n. - Clark Kimberling, Jan 20 2014
a(n) is the number of partitions p of n+1 such that 2*max(p) > n+1. - Clark Kimberling, Apr 20 2014.
From Gus Wiseman, Nov 28 2018: (Start)
Also the number of integer partitions of n + 2 that are the vertex-degrees of some hypertree. For example, the a(6) = 7 partitions of 8 that are the vertex-degrees of some hypertree, together with a realizing hypertree are:
     (41111): {{1,2},{1,3},{1,4},{1,5}}
     (32111): {{1,2},{1,3},{1,4},{2,5}}
     (22211): {{1,2},{1,3},{2,4},{3,5}}
    (311111): {{1,2},{1,3},{1,4,5,6}}
    (221111): {{1,2},{1,3},{2,4,5,6}}
   (2111111): {{1,2},{1,3,4,5,6,7}}
  (11111111): {{1,2,3,4,5,6,7,8}}
(End)
Conjecture: a(n) is the length of maximal initial segment of A308355(n-1) that is identical to row n of A128628, for n >= 2. - Clark Kimberling, May 24 2019
From Gus Wiseman, May 21 2021: (Start)
The Heinz numbers of palindromic partitions are given by A265640. The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.
Also the number of integer partitions of n with a part greater than or equal to n/2. This is equivalent to Clark Kimberling's final comment above. The Heinz numbers of these partitions are given by A344414. For example, the a(1) = 1 through a(8) = 12 partitions are:
  (1)  (2)   (3)   (4)    (5)    (6)     (7)     (8)
       (11)  (21)  (22)   (32)   (33)    (43)    (44)
                   (31)   (41)   (42)    (52)    (53)
                   (211)  (311)  (51)    (61)    (62)
                                 (321)   (421)   (71)
                                 (411)   (511)   (422)
                                 (3111)  (4111)  (431)
                                                 (521)
                                                 (611)
                                                 (4211)
                                                 (5111)
                                                 (41111)
Also the number of integer partitions of n with at least n/2 parts. The Heinz numbers of these partitions are given by A344296. For example, the a(1) = 1 through a(8) = 12 partitions are:
  (1)  (2)   (21)   (22)    (221)    (222)     (2221)     (2222)
       (11)  (111)  (31)    (311)    (321)     (3211)     (3221)
                    (211)   (2111)   (411)     (4111)     (3311)
                    (1111)  (11111)  (2211)    (22111)    (4211)
                                     (3111)    (31111)    (5111)
                                     (21111)   (211111)   (22211)
                                     (111111)  (1111111)  (32111)
                                                          (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
(End)

			The partitions for the first few values of n are as follows:
n: partitions .......................... number
1: 1 ................................... 1
2: 2 11 ................................ 2
3: 3 111 ............................... 2
4: 4 22 121 1111 ....................... 4
5: 5 131 212 11111 ..................... 4
6: 6 141 33 222 1221 11211 111111 ...... 7
7: 7 151 313 11311 232 21112 1111111 ... 7
From _Reinhard Zumkeller_, Jan 23 2010: (Start)
Partitions into 1,2,4,6,... for the first values of n:
1: 1 ....................................... 1
2: 2 11 .................................... 2
3: 21 111 .................................. 2
4: 4 22 211 1111 ........................... 4
5: 41 221 2111 11111 ....................... 4
6: 6 42 4211 222 2211 21111 111111.......... 7
7: 61 421 42111 2221 22111 211111 1111111 .. 7. (End)

David A. Corneth, Table of n, a(n) for n = 0..10000 (first 101 terms from Reinhard Zumkeller that were corrected by _Georg Fischer_, Jan 20 2019)

Cf. A172033, A004277. - Reinhard Zumkeller, Jan 23 2010
Cf. A004526, A030019, A056503, A147878, A320921, A322136.
The bisections are both A000070.
The ordered version (palindromic compositions) is A016116.
The complement is counted by A233771 and A210249.
The case of palindromic prime signature is A242414.
Palindromic partitions are ranked by A265640, with complement A229153.
The case of palindromic plane trees is A319436.
The multiplicative version (palindromic factorizations) is A344417.
A000569 counts graphical partitions.
A027187 counts partitions of even length, ranked by A028260.
A035363 counts partitions into even parts, ranked by A066207.
A058696 counts partitions of even numbers, ranked by A300061.
A110618 counts partitions with length <= half sum, ranked by A344291.
Cf. A000041, A067538, A143773, A209816, A338914, A338915, A340387, A344296, A344414, A344415, A344416.

a025065 = p (1:[2,4..]) where
   p [] _ = 0
   p _  0 = 1
   p ks'@(k:ks) m | m < k     = 0
                  | otherwise = p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Aug 12 2011

import Data.List (group)
a025065 = length . filter (<= 1) .
                   map (sum . map ((`mod` 2) . length) . group) . ps 1
   where ps x 0 = [[]]
         ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]
-- Reinhard Zumkeller, Dec 18 2013

Map[Length[Select[IntegerPartitions[#], Count[OddQ[Transpose[Tally[#]][[2]]], True] <= 1 &]] &, Range[40]] (* Peter J. C. Moses, Jan 20 2014 *)
n = 8; Select[IntegerPartitions[n], Count[OddQ[Transpose[Tally[#]][[2]]], True] <= 1 &] (* Peter J. C. Moses, Jan 20 2014 *)
CoefficientList[Series[1/((1 - x) Product[1 - x^(2 n), {n, 1, 50}]), {x, 0, 60}], x] (* Clark Kimberling, Mar 14 2014 *)

N=66; q='q+O('q^N); Vec( 1/((1-q)*eta(q^2)) ) \\ Joerg Arndt, Mar 11 2014

a(n) = A000070(A004526(n)). - Reinhard Zumkeller, Jan 23 2010
G.f.: 1/((1-q)*prod(n>=1, 1-q^(2*n))). [Joerg Arndt, Mar 11 2014]
a(2*k+2) = a(2*k) + A000041(k + 1). - David A. Corneth, May 29 2021
a(n) ~ exp(Pi*sqrt(n/3)) / (2*Pi*sqrt(n)). - Vaclav Kotesovec, Nov 16 2021

Edited by N. J. A. Sloane, Dec 29 2007

Prepended a(0)=1, added more terms, Joerg Arndt, Mar 11 2014

A265640 Prime factorization palindromes (see comments for definition).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16, 17, 18, 19, 20, 23, 25, 27, 28, 29, 31, 32, 36, 37, 41, 43, 44, 45, 47, 48, 49, 50, 52, 53, 59, 61, 63, 64, 67, 68, 71, 72, 73, 75, 76, 79, 80, 81, 83, 89, 92, 97, 98, 99, 100, 101, 103, 107, 108, 109, 112, 113, 116, 117, 121, 124, 125, 127, 128, 131, 137, 139, 144

Offset: 1

Vladimir Shevelev, Dec 11 2015

nonn

a(66) is the first term at which this sequence differs from A119848.
A number N is called a prime factorization palindrome (PFP) if all its prime factors, taking into account their multiplicities, can be arranged in a row with central symmetry (see example). It is easy to see that every PFP-number is either a square or a product of a square and a prime. In particular, the sequence contains all primes.
Numbers which are both palindromes (A002113) and PFP are 1,2,3,4,5,7,9,11,44,99,101,... (see A265641).
If n is in the sequence, so is n^k for all k >= 0. - Altug Alkan, Dec 11 2015
The sequence contains all perfect numbers except 6 (cf. A000396). - Don Reble, Dec 12 2015
Equivalently, numbers that have at most one prime factor with odd multiplicity. - Robert Israel, Feb 03 2016
Numbers whose squarefree part is noncomposite. - Peter Munn, Jul 01 2020

			44 is a member, since 44=2*11*2.
52 is a member, since 52=2*13*2. [This illustrates the fact that the digits don't need to form a palindrome. This is not a base-dependent sequence. - _N. J. A. Sloane_, Oct 05 2024]
180 is a member, since 180=2*3*5*3*2.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000396, A000720, A002113, A265641, complement of A229153.
Disjoint union of A229125 and (A000290\{0}).
Cf. A013661 (zeta(2)).

N:= 1000: # to get all terms <= N
P:= [1,op(select(isprime, [2,seq(i,i=3..N,2)]))]:
sort([seq(seq(p*x^2,x=1..floor(sqrt(N/p))),p=P)]); # Robert Israel, Feb 03 2016

M = 200; P = Join[{1}, Select[Join[{2}, Range[3, M, 2]], PrimeQ]]; Sort[ Flatten[Table[Table[p x^2, {x, 1, Floor[Sqrt[M/p]]}], {p, P}]]] (* Jean-François Alcover, Apr 09 2019, after Robert Israel *)

for(n=1, 200, if( ispseudoprime(core(n)) || issquare(n), print1(n, ", "))) \\ Altug Alkan, Dec 11 2015

from math import isqrt
from sympy.ntheory.factor_ import core, isprime
def ok(n): return isqrt(n)**2 == n or isprime(core(n))
print([k for k in range(1, 145) if ok(k)]) # Michael S. Branicky, Oct 03 2024

from math import isqrt
from sympy import primepi, mobius
def A265640(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):
        c = n-(a:=isqrt(x))
        for y in range(1,a+1):
            m = x//y**2
            c -= primepi(m)-sum(mobius(k)*(m//k**2) for k in range(1, isqrt(m)+1))
        return c
    return bisection(f,n,n) # Chai Wah Wu, Jan 30 2025

lim A(x)/pi(x) = zeta(2) where A(x) is the number of a(n) <= x and pi is A000720.

A229125 Numbers of the form p * m^2, where p is prime and m > 0: union of A228056 and A000040.

Original entry on oeis.org

2, 3, 5, 7, 8, 11, 12, 13, 17, 18, 19, 20, 23, 27, 28, 29, 31, 32, 37, 41, 43, 44, 45, 47, 48, 50, 52, 53, 59, 61, 63, 67, 68, 71, 72, 73, 75, 76, 79, 80, 83, 89, 92, 97, 98, 99, 101, 103, 107, 108, 109, 112, 113, 116, 117, 124, 125, 127, 128, 131, 137, 139, 147, 148, 149

Offset: 1

Chris Boyd, Sep 14 2013

nonn

No term is the product of two other terms.
Squares of terms and pairwise products of distinct terms form a subsequence of A028260.
Numbers n such that A162642(n) = 1. - Jason Kimberley, Oct 10 2016
Numbers k such that A007913(k) is a prime number. - Amiram Eldar, Jul 27 2020

Chris Boyd, Table of n, a(n) for n = 1..10000
Eckford Cohen, Arithmetical notes, IX. On the set of integers representable as a product of a prime and square, Acta Arithmetica, Vol. 7 (1962), pp. 417-420.

Subsequence of A026424.
Cf. A028260, A162642, A229153.
Cf. A007913, A013661.
Subsequences: A000040, A030078, A050997, A054753, A092759, A179643, A179665, A246551.

With[{nn=70},Take[Union[Flatten[Table[p*m^2,{p,Prime[Range[nn]]},{m,nn}]]], nn]] (* Harvey P. Dale, Dec 02 2014 *)

test(n)=isprime(core(n))
for(n=1,200,if(test(n), print1(n",")))

from math import isqrt
from sympy import primepi
def A229125(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+x-sum(primepi(x//y**2) for y in range(1,isqrt(x)+1))
    return bisection(f,n,n) # Chai Wah Wu, Jan 30 2025

The number of terms not exceeding x is (Pi^2/6) * x/log(x) + O(x/(log(x))^2) (Cohen, 1962). - Amiram Eldar, Jul 27 2020

A048943 Product of divisors of n is a square.

Original entry on oeis.org

1, 6, 8, 10, 14, 15, 16, 21, 22, 24, 26, 27, 30, 33, 34, 35, 38, 39, 40, 42, 46, 51, 54, 55, 56, 57, 58, 60, 62, 65, 66, 69, 70, 72, 74, 77, 78, 81, 82, 84, 85, 86, 87, 88, 90, 91, 93, 94, 95, 96, 102, 104, 105, 106, 108, 110, 111, 114, 115, 118, 119, 120

Offset: 1

Eric W. Weisstein

nonn

From Gerard P. Michon, Oct 10 2010: (Start)
If d is the number of divisors of N, a prime factor of N with multiplicity k in N has a multiplicity kd/2 in the product of all divisors of N (including N itself). Therefore the latter is a square if and only if kd/2 is always even (which is to say that kd is a multiple of 4 for any multiplicity k of a prime factor of N). This happens when one of the following three conditions hold:
- N is a fourth power (all the multiplicities are then multiples of 4 and d is odd).
- N has at least two prime factors with odd multiplicities.
- N has (at least) one prime factor with a multiplicity congruent to 3 modulo 4.
(End)
It follows from the comment above that if two terms are: a) even and odd, or b) terms of A006881, or c) terms of A000583, then their product is also a term. - Ivan N. Ianakiev, Jul 02 2023

			From _Gerard P. Michon_, Oct 10 2010: (Start)
a(1) = 1 because it's a fourth power. The product of all divisors of 1 is 1, which is a square.
a(2) = 6 because 2^1.3^1 is the product of two primes with odd multiplicities (1 in both cases). Indeed, the divisor product 1.2.3.6 = 36 is a square.
a(3) = 8 because 2 is a prime factor of 8 with multiplicity 3. Indeed, 1.2.4.8 = 64 is a square.
a(7) = 16 because it's a fourth power; 1.2.4.8.16 = 1024 is the square of 32. (End)

T. D. Noe, Table of n, a(n) for n = 1..1000
G. P. Michon, Divisor Product, Numericana.
Eric Weisstein's World of Mathematics, Divisor Product

Supersequence of A229153.

Select[Range[125], IntegerQ[Sqrt[Times @@ Divisors[#]]] &] (* T. D. Noe, Apr 30 2012 *)

{for(k=1, 126, mpc=1;
M=divisors(k);
for(i=1, matsize(M)[2], mpc=mpc*M[i]);
if(issquare(mpc), print1(k, ", ")))} \\\ Douglas Latimer, Apr 30 2012

is(n)=my(f=factor(n)[,2]); gcd(f)%4==0 || #select(k->k%2, f)>1 || #select(k->k%4==3, f) \\ Charles R Greathouse IV, Sep 18 2015

from sympy import divisor_count
from gmpy2 import iroot
A048943_list = [i for i in range(1,10**3) if iroot(i,4)[1] or not divisor_count(i) % 4] # Chai Wah Wu, Mar 10 2016

[n for n in (1..125) if prod(divisors(n)).is_square()] # Giuseppe Coppoletta, Dec 16 2014

A119847 Positions where A119842 is zero.

Original entry on oeis.org

6, 10, 14, 15, 21, 22, 24, 26, 30, 33, 34, 35, 38, 39, 40, 42, 46, 51, 54, 55, 56, 57, 58, 60, 62, 65, 66, 69, 70, 74, 77, 78, 82, 84, 85, 86, 87, 88, 90, 91, 93, 94, 95, 96, 102, 104, 105, 106, 110, 111, 114, 115, 118, 119, 122, 123, 126, 129, 130, 132, 133, 134

Offset: 1

Antti Karttunen, Jun 04 2006

nonn

In addition to the terms of A119899 includes also terms with prime signature p*q*r, e.g. 30 (= 2*3*5). Anything else?

Alois P. Heinz, Table of n, a(n) for n = 1..6677

Complement: A119848. Superset of A119899. Cf. A119850.

Cf. A229153.

b[s_, t_] := b[s, t] = If[Length[s] < 1, 1, Sum[If[Mod[PrimeOmega[x], 2] == 1 - t && Length[Select[s, Mod[#, x] == 0 &]] == 1, b[s~Complement~{x}, 1 - t], 0], {x, s}]]; c[n_] := Module[{l, m}, l = Sort[FactorInteger[n], #1[[2]] > #2[[2]] &]; m = Product[Prime[i]^l[[i]][[2]], {i, 1, Length[l]} ]; b[Divisors[m][[2 ;; -2]], Mod[PrimeOmega[m], 2]]]; A119847 = Position[ Table[c[n], {n, 1, 200}], 0] // Flatten (* Jean-François Alcover, Mar 03 2016, after Alois P. Heinz *)

A344417 Number of palindromic factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 4, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 4, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 7, 1, 1, 1, 2, 1, 1, 1, 5, 1, 1, 2, 2, 1, 1, 1, 4, 4, 1, 1, 2, 1, 1, 1

Offset: 1

Gus Wiseman, May 22 2021

nonn

A palindrome is a sequence that is the same whether it is read forward or in reverse. A palindromic factorization of n is a finite multiset of positive integers > 1 with product n that can be permuted into a palindrome.

			The palindromic factorizations for n = 2, 4, 16, 36, 64, 144:
  (2)  (4)    (16)       (36)       (64)           (144)
       (2*2)  (4*4)      (6*6)      (8*8)          (12*12)
              (2*2*4)    (2*2*9)    (4*4*4)        (4*4*9)
              (2*2*2*2)  (3*3*4)    (2*2*16)       (4*6*6)
                         (2*2*3*3)  (2*2*4*4)      (2*2*36)
                                    (2*2*2*2*4)    (3*3*16)
                                    (2*2*2*2*2*2)  (2*2*6*6)
                                                   (3*3*4*4)
                                                   (2*2*2*2*9)
                                                   (2*2*3*3*4)
                                                   (2*2*2*2*3*3)

Positions of 1's are A005117.
The case of palindromic compositions is A016116.
The additive version (palindromic partitions) is A025065.
The case of palindromic prime signature is A242414.
The case of palindromic plane trees is A319436.
A001055 counts factorizations.
A229153 ranks non-palindromic partitions.
A265640 ranks palindromic partitions.
Cf. A000041, A000070, A000188, A004526, A030229, A056503, A057567, A082293, A344414.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
palQ[y_]:=Select[Permutations[y],#==Reverse[#]&]!={};
Table[Length[Select[facs[n],palQ]],{n,50}]

a(2^n) = A025065(n).

a(n) = A057567(A000188(n)). - Andrew Howroyd, May 22 2021

cp's OEIS Frontend

A025065 Number of palindromic partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Mathematica

PARI

Formula

Extensions

A265640 Prime factorization palindromes (see comments for definition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A229125 Numbers of the form p * m^2, where p is prime and m > 0: union of A228056 and A000040.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A048943 Product of divisors of n is a square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Sage

A119847 Positions where A119842 is zero.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A344417 Number of palindromic factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula