A007055 -id:A007055 - cp's OEIS frontend

A284873 Array read by antidiagonals: T(n,k) = number of double palindromes of length n using a maximum of k different symbols.

1, 2, 1, 3, 4, 1, 4, 9, 8, 1, 5, 16, 21, 16, 1, 6, 25, 40, 57, 32, 1, 7, 36, 65, 136, 123, 52, 1, 8, 49, 96, 265, 304, 279, 100, 1, 9, 64, 133, 456, 605, 880, 549, 160, 1, 10, 81, 176, 721, 1056, 2125, 1768, 1209, 260, 1, 11, 100, 225, 1072, 1687, 4356, 4345, 4936, 2127, 424, 1

Offset: 1

Andrew Howroyd, Apr 04 2017

A double palindrome is a concatenation of two palindromes.
Also, number of words of length n using a maximum of k different symbols that are rotations of their reversals.
The sequence A165135 (number of n-digit positive papaya numbers) is 9/10 of the value of column 10.
All rows are polynomials of degree 1 + floor(n/2). - Andrew Howroyd, Oct 10 2017
From Petros Hadjicostas, Oct 27 2017: (Start)
Following Kemp (1982), we note that the formula by A. Howroyd below is equivalent to r(n,k) = Sum_{d|n} phi(d)*T(n/d,k), where r(2d, k) = d*(k+1)*k^d and r(2d+1, k) = (2d+1)*k^(d+1). Inverting (according to the theory of Dirichlet convolutions) we get T(n,k) = Sum_{d|n} phi^{(-1)}(d)*r(n/d,k), where phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function.
We can easily prove that Sum_{n>=1} r(n,k)*x^n = R(k,x) = k*x*(x+1)*(k*x+1)/(1-k*x^2)^2 (for each k>=1). We also have Sum_{n>=1} T(n,k)*x^n = Sum_{n>=1} Sum_{d|n} phi^{(-1)}(d)*r(n/d,k)*x^n. Letting m = n/d and noting that x^n = (x^d)^m, we can easily get the g.f. given in the formula section.
Note that r(n,1) = n, r(n,2) = A187272(n), r(n,3) = A187273(n), r(n,4) = A187274(n), and r(n,5) = A187275(n).
(End)

			Table starts:
  1   2    3     4     5      6      7       8       9      10 ...
  1   4    9    16    25     36     49      64      81     100 ...
  1   8   21    40    65     96    133     176     225     280 ...
  1  16   57   136   265    456    721    1072    1521    2080 ...
  1  32  123   304   605   1056   1687    2528    3609    4960 ...
  1  52  279   880  2125   4356   7987   13504   21465   32500 ...
  1 100  549  1768  4345   9036  16765   28624   45873   69940 ...
  1 160 1209  4936 14665  35736  75985  146224  260721  437680 ...
  1 260 2127  9112 27965  69756 150955  294512  530937  899380 ...
  1 424 4689 25216 93025 270936 670369 1471744 2948481 5494600 ...
From _Petros Hadjicostas_, Oct 27 2017: (Start)
We explain how to use the above formulae to find general expressions for some rows.
If p is an odd prime, then phi^{(-1)}(p) = 1-p. Since, also, phi^{(-1)}(1) = 1, we get T(p,k) = (1-p)*k+p*k^{(p+1)/2} for the p-th row above.
If m is a positive integer, then phi^{(-1)}(2^m) = -1, and so T(2^m,k) = 1+(k+1)*(2^{m-1}*k^{2^{m-1}}-1-Sum_{0<=s<=m-2} 2^s*k^{2^s}).
For example, if m=1, then T(2,k) = 1+(k+1)*(1*k-1-0) = k^2.
If m=2, then T(4,k) = 1+(k+1)*(2*k^2-1-k) = k*(2*k^2+k-2), which is the formula conjectured by C. Barker for sequence A187277 and verified by A. Howroyd.
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Chuan Guo, J. Shallit, and A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Columns 2-5 are A007055, A007056, A007057, A007058.
Rows 3-4 are A000567, A187277.
Cf. A023900, A165137, A165135.

r[d_, k_]:=If[OddQ[d], d*k^((d + 1)/2), (d/2)*(k + 1)*k^(d/2)]; a[n_, k_]:= r[n, k] - Sum[If[dIndranil Ghosh, Apr 07 2017 *)

r(d,k)=if (d % 2 == 0, (d/2)*(k+1)*k^(d/2), d*k^((d+1)/2));
a(n,k) = r(n,k) - sumdiv(n,d, if (d

from sympy import totient, divisors
def r(d, k): return (d//2)*(k + 1)*k**(d//2) if d%2 == 0 else d*k**((d + 1)//2)
def a(n, k): return r(n, k) - sum([totient(n//d)*a(d, k) for d in divisors(n) if dIndranil Ghosh, Apr 07 2017

T(n, k) = r(n, k) - Sum_{d|n, d

From Petros Hadjicostas, Oct 27 2017: (Start)

T(n,k) = Sum_{d|n} phi^{(-1)}(d)*r(n/d,k), where r(n,k) is given above and phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function.

G.f.: For each k>=1, Sum_{n>=1} T(n,k)*x^n = Sum_{d>=1} phi^{(-1)}(d)*R(k,x^d), where R(k,x) = k*x*(x+1)*(k*x+1)/(1-k*x^2)^2.

(End)

From Richard L. Ollerton, May 07 2021: (Start)

T(n,k) = Sum_{i=1..n} phi^{(-1)}(n/gcd(n,i))*r(gcd(n,i),k)/phi(n/gcd(n,i)).

T(n,k) = Sum_{i=1..n} phi^{(-1)}(gcd(n,i))*r(n/gcd(n,i),k)/phi(n/gcd(n,i)).

r(n,k) = Sum_{i=1..n} T(gcd(n,i),k). (End)

A165135 The number of n-digit positive papaya numbers.

Original entry on oeis.org

9, 90, 252, 1872, 4464, 29250, 62946, 393912, 809442, 4945140, 9899910, 59366286, 116999892, 692936460, 1349989992, 7919601912, 15299999856, 89099130960, 170999999838, 989995038012, 1889999872488, 10889990099100, 20699999999802, 118799939782206, 224999999981964

Offset: 1

Sergei Bernstein and Tanya Khovanova, Sep 04 2009

Papaya numbers are concatenations of two palindromes or palindromes themselves. All one-digit and two-digit numbers are papaya numbers.

			Three-digit papaya numbers are of four types: aaa (total of 9) and aab, aba, abb, (total of 81 for each). Hence a(3) = 252.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Tanya Khovanova, Papaya Words and Numbers

Cf. A007055, A052268, A165610, A165611.

R(n,b)=if(n%2==0, n/2*(b+1)*b^(n/2), n*b^((n+1)/2));
a(n) = 9*R(n,10)/10 - sumdiv(n, d, if(n<>d, eulerphi(n/d)*a(d))); \\ Andrew Howroyd, Oct 14 2017

from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A165135(n): return 9*(n*10**(n>>1) if n&1 else 11*(a:=n>>1)*10**(a-1))-sum(totient(n//d)*A165135(d) for d in proper_divisors(n,generator=True)) # Chai Wah Wu, Feb 19 2024

a(n) = A052268(n)-A165611(n). - R. J. Mathar, Sep 25 2009

a(n) = 9*R(n,10)/10 - Sum_{d|n,dAndrew Howroyd, Mar 29 2016

a(7)-a(8) from R. J. Mathar, Sep 25 2009

a(9)-a(25) from Andrew Howroyd, Mar 29 2016

A187272 a(n) = (n/4)2^(n/2)((1+sqrt(2))^2 + (-1)^n*(1-sqrt(2))^2).

Original entry on oeis.org

0, 2, 6, 12, 24, 40, 72, 112, 192, 288, 480, 704, 1152, 1664, 2688, 3840, 6144, 8704, 13824, 19456, 30720, 43008, 67584, 94208, 147456, 204800, 319488, 442368, 688128, 950272, 1474560, 2031616, 3145728, 4325376, 6684672, 9175040, 14155776, 19398656, 29884416, 40894464, 62914560, 85983232

Offset: 0

N. J. A. Sloane, Mar 07 2011

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234. See Lemma 6 (p. 228).
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-4).

Cf. A187273, A187274, A187275.

Cf. A007055, A007056, A007057, A007058.

[Round((n/4)*2^(n/2)*((1+Sqrt(2))^2 + (-1)^n*(1-Sqrt(2))^2)): n in [0..30]]; // G. C. Greubel, Nov 28 2017

R:=(b,n)-> expand(simplify( (n/4)*b^(n/2)*((1+sqrt(b))^2+(-1)^n*(1-sqrt(b))^2) ));
[seq(R(2,n),n=0..100)];

CoefficientList[Series[2 x (1 + x) (1 + 2 x) / (1 - 2 x^2)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Jun 19 2013 *)

x='x+O('x^30); concat([0], Vec(2*x*(1+x)*(1+2*x)/(1-2*x^2)^2)) \\ G. C. Greubel, Nov 28 2017

def A187272(n): return (n<<(n+1>>1) if n&1 else 3*n<<(n-2>>1)) if n else 0 # Chai Wah Wu, Feb 18 2024

From Bruno Berselli, Mar 22 2011: (Start)
G.f.: 2*x*(1+x)*(1+2*x)/(1-2*x^2)^2.
a(n)/a(n-2) = 2*n/(n-2). (End)
a(2*n) = 3*n*2^n, a(2*n+1) = (2*n+1)*2^(n+1). - Andrew Howroyd, Mar 28 2016

A007056 Let S denote the palindromes in the language {0,1,2}*; a(n) = number of words of length n in the language SS.

Original entry on oeis.org

1, 3, 9, 21, 57, 123, 279, 549, 1209, 2127, 4689, 7989, 17031, 28395, 60615, 98061, 208569, 334563, 705789, 1121877, 2356737, 3718827, 7786359, 12223077, 25488903, 39857523, 82876257, 129135729, 267784119, 416118219, 860825439, 1334448261, 2754778809, 4261609131, 8781196329, 13559714109, 27893530029

Offset: 0

N. J. A. Sloane, Mira Bernstein, R. Kemp

nonn

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

R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Column 3 of A284873.

Maple
```
See A007055.
```

from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A007056(n): return (n*3**(1+(n>>1)) if n&1 else (n<<1)*3**(n>>1))-sum(totient(n//d)*A007056(d) for d in proper_divisors(n,generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024

a(n) = A187273(n) - Sum_{d|n,dSean A. Irvine, Sep 27 2017

Entry revised by N. J. A. Sloane, Mar 07 2011

A007057 Let S denote the palindromes in the language {0,1,2,3}*; a(n) = number of words of length n in the language SS.

Original entry on oeis.org

1, 4, 16, 40, 136, 304, 880, 1768, 4936, 9112, 25216, 45016, 121600, 212944, 571552, 982240, 2616136, 4456384, 11785408, 19922872, 52402336, 88076560, 230641504, 385875880, 1006499200, 1677720304, 4361862976, 7247738776, 18789905872, 31138512784, 80529599680, 133143986056, 343594756936

Offset: 0

N. J. A. Sloane, Mira Bernstein, R. Kemp

nonn

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

R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Column 4 of A284873.

Maple
```
See A007055.
```

from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A007057(n): return (n<>1)<A007057(d) for d in proper_divisors(n,generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024

a(n) = A187274(n) - Sum_{d|n,dSean A. Irvine, Sep 27 2017

Entry revised by N. J. A. Sloane, Mar 07 2011

A007058 Let S denote the palindromes in the language {0,1,2,3,4}*; a(n) = number of words of length n in the language SS.

Original entry on oeis.org

1, 5, 25, 65, 265, 605, 2125, 4345, 14665, 27965, 93025, 171825, 559645, 1015565, 3276725, 5857865, 18734665, 33203045, 105436225, 185546785, 585842065, 1025381485, 3222484125, 5615234265, 17577530845, 30517575605, 95213827825, 164794865465, 512692025285, 885009765485, 2746575977125

Offset: 0

N. J. A. Sloane, Mira Bernstein, R. Kemp

nonn

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

R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Column 5 of A284873.

Cf. A007055, A007056, A007057.

Maple
```
See A007055.
```

from functools import lru_cache
from sympy import totient, proper_divisors
@lru_cache(maxsize=None)
def A007058(n): return (n*5**(1+(n>>1)) if n&1 else 3*n*5**(n>>1))-sum(totient(n//d)*A007058(d) for d in proper_divisors(n,generator=True)) if n else 1 # Chai Wah Wu, Feb 19 2024

a(n) = A187275(n) - Sum_{d|n,dSean A. Irvine, Sep 27 2017

Entry revised by N. J. A. Sloane, Mar 07 2011

A187277 Let S denote the palindromes in the language {0,1,2,...,n-1}*; a(n) = number of words of length 4 in the language SS.

Original entry on oeis.org

1, 16, 57, 136, 265, 456, 721, 1072, 1521, 2080, 2761, 3576, 4537, 5656, 6945, 8416, 10081, 11952, 14041, 16360, 18921, 21736, 24817, 28176, 31825, 35776, 40041, 44632, 49561, 54840, 60481, 66496, 72897, 79696, 86905, 94536, 102601, 111112, 120081, 129520, 139441, 149856, 160777, 172216, 184185

Offset: 1

N. J. A. Sloane, Mar 07 2011

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000
R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234. See Table 1.

Row 4 of A284873.

[2*n^3 + n^2 - 2*n: n in [1..50]]; // G. C. Greubel, Jul 25 2018

Using the Maple code from A007055: [seq(F(b,4),b=1..50)];

Array[# (2 #^2 + # - 2) &, 45] (* or *)
Rest@ CoefficientList[Series[-x (x^2 - 12 x - 1)/(x - 1)^4, {x, 0, 45}], x] (* Michael De Vlieger, Oct 10 2017 *)

a(n) = 2*n^3 + n^2 - 2*n; \\ Andrew Howroyd, Oct 10 2017

def A187277(n): return n*(n*((n<<1)|1)-2) # Chai Wah Wu, Feb 19 2024

From Colin Barker, Jul 24 2013: (Start) (Conjectured formulas; later proven)
a(n) = n*(2*n^2 +n -2).
G.f.: x*(1 +12*x - x^2)/(x-1)^4. (End)
The above conjecture is true: A284873(4, n) evaluates to the same polynomial. - Andrew Howroyd, Oct 10 2017

A370410 Number of length-n binary strings that are the concatenation of two nonempty palindromes.

Original entry on oeis.org

0, 4, 6, 14, 26, 48, 86, 148, 232, 400, 622, 982, 1514, 2440, 3482, 5680, 8162, 12932, 18398, 29146, 40706, 64856, 90070, 141880, 196448, 309712, 425412, 668978, 917450, 1437148, 1966022, 3074080, 4192882, 6545344, 8912278, 13877920, 18874298, 29341624, 39842594, 61835140, 83886002, 129977116, 176160686, 272563362

Offset: 1

Jeffrey Shallit, Feb 18 2024

nonn

a(6618) has 1001 digits. - Michael S. Branicky, Feb 21 2024

Michael S. Branicky, Table of n, a(n) for n = 1..6617
Michael S. Branicky, Python program for A370410 (bitwise operations)
Michael S. Branicky, Python program for A370410 (explicit construction)
R. C. Lyndon and M. P. Schützenberger, The equation a^M = b^N c^P in a free group, Michigan Math. J., 9(4):289-298, 1962.

Cf. A007055 (allows the palindromes to be empty), A056458.

# see below and Links for faster programs
from itertools import product
def p(w): return w == w[::-1]
def c(w): return any(p(w[:i]) and p(w[i:]) for i in range(1, len(w)))
def a(n): return 2*sum(1 for w in product("01", repeat=n-1) if c(("1",)+w))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024

from itertools import product
def bin_pals(d): yield from ("".join(p+(m,)+p[::-1]) for p in product("01", repeat=d//2) for m in [[""], ["0", "1"]][d%2])
def a(n): return len(set(a+b for i in range(1, n) for a in bin_pals(i) for b in bin_pals(n-i)))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024

# uses formula above; functions/imports in A007055, A056458
def a(n): return A007055(n) - A056458(n)
print([a(n) for n in range(1, 45)]) # Michael S. Branicky, Feb 21 2024

a(n) = A007055(n) - A056458(n) (conjectured). - Michael S. Branicky, Feb 18 2024
From Daniel Gabric, Feb 21 2024: (Start)
Proof of the above formula: Let w be a length-n binary string that is the concatenation of two possibly empty palindromes. It suffices to show that w is not the concatenation of two nonempty palindromes iff w is a primitive palindrome.
We prove the forward direction. Suppose w is not the concatenation of two nonempty palindromes. By assumption, w is the concatenation of two possibly empty palindromes. Therefore, w must be a palindrome. Suppose, for the sake of a contradiction, that w is not primitive. Then w = z^i for some nonempty string z and some integer i>=2. But since w is a palindrome, we have that z^i = w = w^R = (z^i)^R = (z^R)^i, which implies z is a palindrome. Thus, w is the concatenation of the nonempty palindromes z and z^(i-1), a contradiction.
Now we prove the backward direction.  Assume, for the sake of a contradiction, that w is a primitive palindrome, and w = uv for some nonempty palindromes u and v. Then uv = w = w^R = (uv)^R = v^Ru^R = vu. By Lemma 3 in a paper of Lyndon and Schützenberger (see links for reference), uv = vu implies w is not primitive, a contradiction. (End)

a(21)-a(44) from Michael S. Branicky, Feb 18 2024

Showing 1-9 of 9 results.

Papaya words are concatenations of two palindromes or palindromes themselves. A165136 is the number of papaya patterns for n-digit numbers. Thus a(n) coincides with A165136 for small n, and is greater than A165136 for larger n. The actual number of n-digit papaya numbers is A165135.

The first 19 terms of this sequence are the same as in A165136. A165137(20) = A165136(20)+10. - Tanya Khovanova, Oct 01 2009, corrected by Franklin T. Adams-Watters, Apr 10 2011

cp's OEIS Frontend

A165137 a(n) is the number of patterns for n-character papaya words in an infinite alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A284873 Array read by antidiagonals: T(n,k) = number of double palindromes of length n using a maximum of k different symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A165135 The number of n-digit positive papaya numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A187272 a(n) = (n/4)*2^(n/2)*((1+sqrt(2))^2 + (-1)^n*(1-sqrt(2))^2).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A007056 Let S denote the palindromes in the language {0,1,2}*; a(n) = number of words of length n in the language SS.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

A007057 Let S denote the palindromes in the language {0,1,2,3}*; a(n) = number of words of length n in the language SS.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

A007058 Let S denote the palindromes in the language {0,1,2,3,4}*; a(n) = number of words of length n in the language SS.

Views

Author

A187272 a(n) = (n/4)2^(n/2)((1+sqrt(2))^2 + (-1)^n*(1-sqrt(2))^2).