A002113 Palindromes in base 10. (Formerly M0484 N0178)

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515

Offset

1,3

Comments

n is a palindrome (i.e., a(k) = n for some k) if and only if n = A004086(n). - Reinhard Zumkeller, Mar 10 2002

It seems that if n*reversal(n) is in the sequence then n = 3 or all digits of n are less than 3. - Farideh Firoozbakht, Nov 02 2014

The position of a palindrome within the sequence can be determined almost without calculation: If the palindrome has an even number of digits, prepend a 1 to the front half of the palindrome's digits. If the number of digits is odd, prepend the value of front digit + 1 to the digits from position 2 ... central digit. Examples: 98766789 = a(19876), 515 = a(61), 8206028 = a(9206), 9230329 = a(10230). - Hugo Pfoertner, Aug 14 2015

This sequence is an additive basis of order at most 49, see Banks link. - Charles R Greathouse IV, Aug 23 2015

The order has been reduced from 49 to 3; see the Cilleruelo-Luca and Cilleruelo-Luca-Baxter links. - Jonathan Sondow, Nov 27 2017

See A262038 for the "next palindrome" and A261423 for the "preceding palindrome" functions. - M. F. Hasler, Sep 09 2015

The number of palindromes with d digits is 10 if d = 1, and otherwise it is 9 * 10^(floor((d - 1)/2)). - N. J. A. Sloane, Dec 06 2015

Sequence A033665 tells how many iterations of the Reverse-then-add function A056964 are needed to reach a palindrome; numbers for which this will never happen are Lychrel numbers (A088753) or rather Kin numbers (A023108). - M. F. Hasler, Apr 13 2019

References

Karl G. Kröber, "Palindrome, Perioden und Chaoten: 66 Streifzüge durch die palindromischen Gefilde" (1997, Deutsch-Taschenbücher; Bd. 99) ISBN 3-8171-1522-9.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.

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

Links

T. D. Noe, List of first 19999 palindromes: Table of n, a(n) for n = 1..19999

Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014.

William D. Banks, Derrick N. Hart, and Mayumi Sakata, Almost all palindromes are composite, Math. Res. Lett., Vol. 11, No. 5-6 (2004), pp. 853-868.

William D. Banks, Every natural number is the sum of forty-nine palindromes, arXiv:1508.04721 [math.NT], 2015; Integers, 16 (2016), article A3.

Javier Cilleruelo, Florian Luca and Lewis Baxter, Every positive integer is a sum of three palindromes, Mathematics of Computation, Vol. 87, No. 314 (2018), pp. 3023-3055, arXiv preprint, arXiv:1602.06208 [math.NT], 2017.

Patrick De Geest, World of Numbers.

Kritkhajohn Onphaeng, Tammatada Khemaratchatakumthorn, Phakhinkon Napp Phunphayap, and Prapanpong Pongsriiam, Exact Formulas for the Number of Palindromes in Certain Arithmetic Progressions, Journal of Integer Sequences, Vol. 27 (2024), Article 24.4.8. See p. 2.

Phakhinkon Phunphayap and Prapanpong Pongsriiam, Reciprocal sum of palindromes, arXiv:1803.00161 [math.CA], 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

Prapanpong Pongsriiam and Kittipong Subwattanachai, Exact Formulas for the Number of Palindromes up to a Given Positive Integer, Intl. J. of Math. Comp. Sci. (2019) 14:1, 27-46.

E. A. Schmidt, Positive Integer Palindromes. [Cached copy at the Wayback Machine]

Eric Weisstein's World of Mathematics, Palindromic Number.

Wikipedia, Palindromic number.

Index entries for sequences that are an additive basis, order 3.

Index entries for sequences related to palindromes

Index entries for "core" sequences

Formula

A136522(a(n)) = 1.

A178788(a(n)) = 0 for n > 9. - Reinhard Zumkeller, Jun 30 2010

A064834(a(n)) = 0. - Reinhard Zumkeller, Sep 18 2013

a(n+1) = A262038(a(n)+1). - M. F. Hasler, Sep 09 2015

Sum_{n>=2} 1/a(n) = A118031. - Amiram Eldar, Oct 17 2020

Maple

read transforms; t0:=[]; for n from 0 to 2000 do if digrev(n) = n then t0:=[op(t0), n]; fi; od: t0;
# Alternatively, to get all palindromes with <= N digits in the list "Res":
N:=5;
Res:= $0..9:
for d from 2 to N do
  if d::even then
    m:= d/2;
    Res:= Res, seq(n*10^m + digrev(n), n=10^(m-1)..10^m-1);
  else
    m:= (d-1)/2;
    Res:= Res, seq(seq(n*10^(m+1)+y*10^m+digrev(n), y=0..9), n=10^(m-1)..10^m-1);
  fi
od: Res:=[Res]: # Robert Israel, Aug 10 2014
# A variant: Gets all base-10 palindromes with exactly d digits, in the list "Res"
d:=4:
if d=1 then Res:= [$0..9]:
elif d::even then
    m:= d/2:
    Res:= [seq(n*10^m + digrev(n), n=10^(m-1)..10^m-1)]:
else
    m:= (d-1)/2:
    Res:= [seq(seq(n*10^(m+1)+y*10^m+digrev(n), y=0..9), n=10^(m-1)..10^m-1)]:
fi:
Res; # N. J. A. Sloane, Oct 18 2015
isA002113 := proc(n)
    simplify(digrev(n) = n) ;
end proc: # R. J. Mathar, Sep 09 2015

Mathematica

palQ[n_Integer, base_Integer] := Module[{idn = IntegerDigits[n, base]}, idn == Reverse[idn]]; (* then to generate any base-b sequence for 1 < b < 37, replace the 10 in the following instruction with b: *) Select[Range[0, 1000], palQ[#, 10] &]
base10Pals = {0}; r = 2; Do[Do[AppendTo[base10Pals, n * 10^(IntegerLength[n] - 1) + FromDigits@Rest@Reverse@IntegerDigits[n]], {n, 10^(e - 1), 10^e - 1}]; Do[AppendTo[base10Pals, n * 10^IntegerLength[n] + FromDigits@Reverse@IntegerDigits[n]], {n, 10^(e - 1), 10^e - 1}], {e, r}]; base10Pals (* Arkadiusz Wesolowski, May 04 2012 *)
nthPalindromeBase[n_, b_] := Block[{q = n + 1 - b^Floor[Log[b, n + 1 - b^Floor[Log[b, n/b]]]], c = Sum[Floor[Floor[n/((b + 1) b^(k - 1) - 1)]/(Floor[n/((b + 1) b^(k - 1) - 1)] - 1/b)] - Floor[Floor[n/(2 b^k - 1)]/(Floor[n/(2 b^k - 1)] - 1/ b)], {k, Floor[Log[b, n]]}]}, Mod[q, b] (b + 1)^c * b^Floor[Log[b, q]] + Sum[Floor[Mod[q, b^(k + 1)]/b^k] b^(Floor[Log[b, q]] - k) (b^(2 k + c) + 1), {k, Floor[Log[b, q]]}]] (* after the work of Eric A. Schmidt, works for all integer bases b > 2 *)
Array[nthPalindromeBase[#, 10] &, 61, 0] (* please note that Schmidt uses a different, a more natural and intuitive offset, that of a(1) = 1. - Robert G. Wilson v, Sep 22 2014 and modified Nov 28 2014 *)
Select[Range[10^3], PalindromeQ] (* Michael De Vlieger, Nov 27 2017 *)

Prog

(PARI) is_A002113(n)=Vecrev(n=digits(n))==n \\ M. F. Hasler, Nov 17 2008, updated Apr 26 2014, Jun 19 2018
(PARI) is(n)=n=digits(n); for(i=1, #n\2, if(n[i]!=n[#n+1-i], return(0))); 1 \\ Charles R Greathouse IV, Jan 04 2013
(PARI) a(n)={my(d, i, r); r=vector(#digits(n-10^(#digits(n\11)))+#digits(n\11)); n=n-10^(#digits(n\11)); d=digits(n); for(i=1, #d, r[i]=d[i]; r[#r+1-i]=d[i]); sum(i=1, #r, 10^(#r-i)*r[i])} \\ David A. Corneth, Jun 06 2014
(PARI) \\ recursive--feed an element a(n) and it gives a(n+1)
nxt(n)=my(d=digits(n)); i=(#d+1)\2; while(i&&d[i]==9, d[i]=0; d[#d+1-i]=0; i--); if(i, d[i]++; d[#d+1-i]=d[i], d=vector(#d+1); d[1]=d[#d]=1); sum(i=1, #d, 10^(#d-i)*d[i]) \\ David A. Corneth, Jun 06 2014
(PARI) \\ feed a(n), returns n.
inv(n)={my(d=digits(n)); q=ceil(#d/2); sum(i=1, q, 10^(q-i)*d[i])+10^floor(#d/2)} \\ David A. Corneth, Jun 18 2014
(PARI) inv_A002113(P)={P\(P=10^(logint(P+!P, 10)\/2))+P} \\ index n of palindrome P = a(n), much faster than above: no sum is needed. - M. F. Hasler, Sep 09 2018
(PARI) A002113(n, L=logint(n, 10))=(n-=L=10^max(L-(n<11*10^(L-1)), 0))*L+fromdigits(Vecrev(digits(if(n<L, n, n\10)))) \\ M. F. Hasler, Sep 11 2018
(Python) # edited by M. F. Hasler, Jun 19 2018
def A002113_list(nMax):
  mlist=[]
  for n in range(nMax+1):
     mstr=str(n)
     if mstr==mstr[::-1]:
        mlist.append(n)
  return mlist # Bill McEachen, Dec 17 2010
(Python)
from itertools import chain
A002113 = sorted(chain(map(lambda x:int(str(x)+str(x)[::-1]), range(1, 10**3)), map(lambda x:int(str(x)+str(x)[-2::-1]), range(10**3)))) # Chai Wah Wu, Aug 09 2014
(Python)
from itertools import chain, count
A002113 = chain(k for k in count(0) if str(k) == str(k)[::-1])
print([next(A002113) for k in range(60)]) # Jan P. Hartkopf, Apr 10 2021
(Python) is_A002113 = lambda n: (s:=str(n))[::-1]==s # M. F. Hasler, May 23 2024
(Python)
from math import log10
def A002113(n):
  if n < 2: return 0
  P = 10**floor(log10(n//2)); M = 11*P
  s = str(n - (P if n < M else M-P))
  return int(s + s[-2 if n < M else -1::-1]) # M. F. Hasler, Jun 06 2024
(Haskell)
  a002113 n = a002113_list !! (n-1)
  a002113_list = filter ((== 1) . a136522) [1..] -- Reinhard Zumkeller, Oct 09 2011
(Haskell)
  import Data.List.Ordered (union)
  a002113_list = union a056524_list a056525_list -- Reinhard Zumkeller, Jul 29 2015, Dec 28 2011
(Magma) [n: n in [0..600] | Intseq(n, 10) eq Reverse(Intseq(n, 10))]; // Vincenzo Librandi, Nov 03 2014
(SageMath)
[n for n in (0..515) if Word(n.digits()).is_palindrome()] # Peter Luschny, Sep 13 2018
(GAP) Filtered([0..550], n->ListOfDigits(n)=Reversed(ListOfDigits(n))); # Muniru A Asiru, Mar 08 2019
(Scala) def palQ(n: Int, b: Int = 10): Boolean = n - Integer.parseInt(n.toString.reverse) == 0
(0 to 999).filter(palQ(_)) // Alonso del Arte, Nov 10 2019

Crossrefs

Palindromes in bases 2 through 11: A006995 and A057148, A014190 and A118594, A014192 and A118595, A029952 and A118596, A029953 and A118597, A029954 and A118598, A029803 and A118599, A029955 and A118600, this sequence, A029956. Also A262065 (base 60), A262069 (subsequence).

Palindromic primes: A002385. Palindromic nonprimes: A032350.

Palindromic-pi: A136687.

Cf. A029742 (complement), A086862 (first differences).

Palindromic floor function: A261423, also A261424. Palindromic ceiling: A262038.

Union of A056524 and A056525.

Cf. A004086 (read n backwards), A064834, A118031, A136522 (characteristic function), A178788.

Ways to write n as a sum of three palindromes: A261132, A261422.

Minimal number of palindromes that add to n using greedy algorithm: A088601.

Minimal number of palindromes that add to n: A261675.

Subsequence of A061917 and A221221.

Subsequence: A110745.

Keyword

nonn,base,easy,nice,core

Author

N. J. A. Sloane

Status

approved

A002385 Palindromic primes: prime numbers whose decimal expansion is a palindrome. (Formerly M0670 N0247)

2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181

Offset

1,1

Comments

Every palindrome with an even number of digits is divisible by 11, so 11 is the only member of the sequence with an even number of digits. - David Wasserman, Sep 09 2004

This holds in any number base A006093(n), n>1. - Lekraj Beedassy, Mar 07 2005 and Dec 06 2009

The log-log plot shows the fairly regular structure of these numbers. - T. D. Noe, Jul 09 2013

Conjecture: The only primes with palindromic prime indices that are palindromic primes themselves are 3, 5 and 11. Tested for the primes with the first 8000000 palindromic prime indices. - Ivan N. Ianakiev, Oct 10 2014

Banks, Hart, and Sakata derive a nontrivial upper bound for the number of prime palindromes n <= x as x -> oo. It follows that almost all palindromes are composite. The results hold in any base. The authors use Weil's bound for Kloosterman sums. - Jonathan Sondow, Jan 02 2018

Number of terms < 100^k: 4, 20, 113, 781, 5953, 47995, 401698, ..., . - Robert G. Wilson v, Jan 03 2018

References

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 228.

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

Links

N. J. A. Sloane, Table of n, a(n) for n = 1..47995 (all palindromic primes with fewer than 12 digits), Oct 14 2015, extending earlier b-files from T. D. Noe and A. Olah.

W. D. Banks, D. N. Hart, and M. Sakata, Almost all palindromes are composite, Math. Res. Lett., 11 No. 5-6 (2004), 853-868.

K. S. Brown, On General Palindromic Numbers

C. K. Caldwell, "Top Twenty" page, Palindrome

Patrick De Geest, World!Of Palindromic Primes

Lubomira Dvorakova, Stanislav Kruml, and David Ryzak, Antipalindromic numbers, arXiv:2008.06864 [math.CO], 2020. Mentions this sequence.

Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.

T. D. Noe, Log-log plot of the first 401696 terms

I. Peterson, Math Trek, Palindromic Primes

Phakhinkon Phunphayap and Prapanpong Pongsriiam, Reciprocal sum of palindromes, arXiv:1803.00161 [math.CA], 2018.

M. Shafer, First 401066 Palprimes [Broken link]

Eric Weisstein's World of Mathematics, Palindromic Number

Eric Weisstein's World of Mathematics, Palindromic Prime

Eric Weisstein's World of Mathematics, Integer Sequence Primes

Wikipedia, Palindromic prime

Index entries for sequences related to palindromes

Formula

Intersection of A000040 (primes) and A002113 (palindromes).

A010051(a(n)) * A136522(a(n)) = 1. [Reinhard Zumkeller, Apr 11 2011]

Complement of A032350 in A002113. - Jonathan Sondow, Jan 02 2018

Maple

ff := proc(n) local i, j, k, s, aa, nn, bb, flag; s := n; aa := convert(s, string); nn := length(aa); bb := ``; for i from nn by -1 to 1 do bb := cat(bb, substring(aa, i..i)); od; flag := 0; for j from 1 to nn do if substring(aa, j..j)<>substring(bb, j..j) then flag := 1 fi; od; RETURN(flag); end; gg := proc(i) if ff(ithprime(i)) = 0 then RETURN(ithprime(i)) fi end;
rev:=proc(n) local nn, nnn: nn:=convert(n, base, 10): add(nn[nops(nn)+1-j]*10^(j-1), j=1..nops(nn)) end: a:=proc(n) if n=rev(n) and isprime(n)=true then n else fi end: seq(a(n), n=1..20000); # rev is a Maple program to revert a number - Emeric Deutsch, Mar 25 2007
# A002385 Gets all base-10 palindromic primes with exactly d digits, in the list "Res"
d:=7; # (say)
if d=1 then Res:= [2, 3, 5, 7]:
elif d=2 then Res:= [11]:
elif d::even then
    Res:=[]:
else
    m:= (d-1)/2:
    Res2 := [seq(seq(n*10^(m+1)+y*10^m+digrev(n), y=0..9), n=10^(m-1)..10^m-1)]:
    Res:=[]: for x in Res2 do if isprime(x) then Res:=[op(Res), x]; fi: od:
fi:
Res; # N. J. A. Sloane, Oct 18 2015

Mathematica

Select[ Prime[ Range[2100] ], IntegerDigits[#] == Reverse[ IntegerDigits[#] ] & ]
lst = {}; e = 3; Do[p = n*10^(IntegerLength[n] - 1) + FromDigits@Rest@Reverse@IntegerDigits[n]; If[PrimeQ[p], AppendTo[lst, p]], {n, 10^e - 1}]; Insert[lst, 11, 5] (* Arkadiusz Wesolowski, May 04 2012 *)
Join[{2, 3, 5, 7, 11}, Flatten[Table[Select[Prime[Range[PrimePi[ 10^(2n)]+1, PrimePi[ 10^(2n+1)]]], # == IntegerReverse[#]&], {n, 3}]]] (* The program uses the IntegerReverse function from Mathematica version 10 *) (* Harvey P. Dale, Apr 22 2016 *)
genPal[n_Integer, base_Integer: 10] := Block[{id = IntegerDigits[n, base], insert = Join[{{}}, {# - 1} & /@ Range[base]]}, FromDigits[#, base] & /@ (Join[id, #, Reverse@id] & /@ insert)]; k = 1; lst = {2, 3, 5, 7}; While[k < 19, p = Select[genPal[k], PrimeQ];
If[p != {}, AppendTo[lst, p]]; k++]; Flatten@ lst (* RGWv *)
Select[ Prime[ Range[2100]], PalindromeQ] (* Jean-François Alcover, Feb 17 2018 *)
NestList[NestWhile[NextPrime, #, ! PalindromeQ[#2] &, 2] &, 2, 41] (* Jan Mangaldan, Jul 01 2020 *)

Prog

(Haskell)
a002385 n = a002385_list !! (n-1)
a002385_list = filter ((== 1) . a136522) a000040_list
-- Reinhard Zumkeller, Apr 11 2011
(PARI) is(n)=n==eval(concat(Vecrev(Str(n))))&&isprime(n) \\ Charles R Greathouse IV, Nov 20 2012
(PARI) forprime(p=2, 10^5, my(d=digits(p, 10)); if(d==Vecrev(d), print1(p, ", "))); \\ Joerg Arndt, Aug 17 2014
(Python)
from itertools import chain
from sympy import isprime
A002385 = sorted((n for n in chain((int(str(x)+str(x)[::-1]) for x in range(1, 10**5)), (int(str(x)+str(x)[-2::-1]) for x in range(1, 10**5))) if isprime(n))) # Chai Wah Wu, Aug 16 2014
(Python)
from sympy import isprime
A002385 = [*filter(isprime, (int(str(x) + str(x)[-2::-1]) for x in range(10**5)))]
A002385.insert(4, 11)  # Yunhan Shi, Mar 03 2023
(Sage)
[n for n in (2..18181) if is_prime(n) and Word(n.digits()).is_palindrome()] # Peter Luschny, Sep 13 2018
(GAP) Filtered([1..20000], n->IsPrime(n) and ListOfDigits(n)=Reversed(ListOfDigits(n))); # Muniru A Asiru, Mar 08 2019

Crossrefs

A007500 = this sequence union A006567.

Subsequence of A188650; A188649(a(n)) = a(n); see A033620 for multiplicative closure. [Reinhard Zumkeller, Apr 11 2011]

Cf. A016041, A029732, A069469, A117697, A046942, A032350 (Palindromic nonprime numbers).

Keyword

nonn,base,nice,easy

Author

N. J. A. Sloane, Simon Plouffe

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Oct 25 2000

Comment from A006093 moved here by Franklin T. Adams-Watters, Dec 03 2009

Status

approved

A006995 Binary palindromes: numbers whose binary expansion is palindromic. (Formerly M2403)

0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 85, 93, 99, 107, 119, 127, 129, 153, 165, 189, 195, 219, 231, 255, 257, 273, 297, 313, 325, 341, 365, 381, 387, 403, 427, 443, 455, 471, 495, 511, 513, 561, 585, 633, 645, 693, 717, 765, 771, 819, 843

Offset

1,3

Comments

If b > 1 is a binary palindrome then both (2^(m+1) + 1)*b and 2^(m+1) + 2^m - b are also, where m = floor(log_2(b)). - Hieronymus Fischer, Feb 18 2012

Floor and ceiling: If d > 0 is any natural number, then A206913(d) is the greatest binary palindrome <= d and A206914(d) is the least binary palindrome >= d. - Hieronymus Fischer, Feb 18 2012

The greatest binary palindrome <= the n-th non-binary-palindrome is that binary palindrome with number A154809(n)-n+1. The corresponding formula identity is: A206913(A154809(n)) = A006995(A154809(n)-n+1). - Hieronymus Fischer, Mar 18 2012

From Hieronymus Fischer, Jan 23 2013: (Start)

The number of binary digits of a(n) is A070939(a(n)) = 1 + floor(log_2(n)) + floor(log_2(n/3)), for n > 1.

Also: A070939(a(n)) = A070939(n) + A070939(floor(n/3)) - 1, for n <> 2. (End)

Rajasekaran, Shallit, & Smith show that this is an additive basis of order 4. - Charles R Greathouse IV, Nov 06 2018

References

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

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

James Haoyu Bai, Joseph Meleshko, Samin Riasat, and Jeffrey Shallit, Quotients of Palindromic and Antipalindromic Numbers, arXiv:2202.13694 [math.NT], 2022.

William D. Banks and Igor E. Shparlinski, Average Value of the Euler Function on Binary Palindromes, Bulletin Polish Acad. Sci. Math., Vol. 54 (2006), pp. 95-101, alternative link.

Manfred Madritsch and Stephan Wagner, A central limit theorem for integer partitions, Monatshefte für Mathematik, Vol. 161, No. 1 (2010), pp. 85-114, alternative link. doi:10.1007/s00605-009-0126-y.

Kritkhajohn Onphaeng, Tammatada Khemaratchatakumthorn, Phakhinkon Napp Phunphayap, and Prapanpong Pongsriiam, Exact Formulas for the Number of Palindromes in Certain Arithmetic Progressions, Journal of Integer Sequences, Vol. 27 (2024), Article 24.4.8. See p. 2.

Aayush Rajasekaran, Using Automata Theory to Solve Problems in Additive Number Theory, MS thesis, University of Waterloo, 2018.

Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, Sums of Palindromes: an Approach via Nested-Word Automata, preprint arXiv:1706.10206 [cs.FL], Jun 30 2017.

Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, Additive Number Theory via Automata Theory, Theory of Computing Systems, Vol. 64 (2020), pp. 542-567.

L. J. Upton, Letter to N. J. A. Sloane with attachments, Oct. 1993.

Index entries for sequences that are an additive basis, order 4.

Index entries for sequences related to binary expansion of n

Index entries for sequences related to palindromes

Formula

A178225(a(n)) = 1; union of A048700 and A048701. - Reinhard Zumkeller, Oct 21 2011

From Hieronymus Fischer, Dec 31 2008, Jan 10 2012, Feb 18 2012: (Start)

Written as a decimal, a(10^n) has 2*n digits. For n > 1, the decimal expansion of a(10^n) starts with 22..., 23... or 24...:

a(1000) = 249903,

a(10^4) = 24183069,

a(10^5) = 2258634081,

a(10^6) = 249410097687,

a(10^7) = 24350854001805,

a(10^8) = 2229543293296319,

a(10^9) = 248640535848971067,

a(10^10)= 24502928886295666773.

Inequality: (2/9)*n^2 < a(n) < (1/4)*(n+1)^2, if n > 1.

lim sup_{n -> oo} a(n)/n^2 = 1/4, lim inf_{n -> oo} a(n)/n^2 = 2/9.

For n >= 2, a(2^n-1) = 2^(2n-2) - 1; a(2^n) = 2^(2n-2) + 1;

a(2^n+1) = 2^(2n-2) + 2^(n-1) + 1; a(2^n + 2^(n-1)) = 2^(2n-1) + 1.

Recursion for n > 2: a(n) = 2^(2k-q) + 1 + 2^p*a(m), where k = floor(log_2(n-1)), and p, q and m are determined as follows:

Case 1: If n = 2^(k+1), then p = 0, q = 0, m = 1;

Case 2: If 2^k < n < 2^k+2^(k-1), then p = k-floor(log_2(i))-1 with i = n-2^k, q = 2, m = 2^floor(log_2(i)) + i;

Case 3: If n = 2^k + 2^(k-1), then p = 0, q = 1, m = 1;

Case 4: If 2^k + 2^(k-1) < n < 2^(k+1), then p = k-floor(log_2(j))-1 with j = n-2^k-2^(k-1), q = 1, m = 2*2^floor(log_2(j))+j.

Non-recursive formula:

Let n >= 3, m = floor(log_2(n)), p = floor((3*2^(m-1)-1)/n), then

a(n) = 2^(2*m-1-p) + 1 + p*(1-(-1)^n)*2^(m-1-p) + sum_{k=1 .. m-1-p} (floor((n-(3-p)*2^(m-1))/2^(m-1-k)) mod 2)*(2^k+2^(2*m-1-p-k)). [Typo at the last exponent of the third sum term eliminated by the author, Sep 05 2018]

a(n) = 2^(2*m-2) + 1 + 2*floor((n-2^m)/2^(m-1)) + 2^(m-1)*floor((1/2)*min(n+1-2^m,2^(m-1)+1)) + 3*2^(m-1)*floor((1/2)*max(n+1-3*2^(m-1),0)) + 3*sum_{j=2 .. m-1} floor((n+2^(j-1)-2^m)/2^j)*2^(m-j). [Seems correct for n > 3. - The Editors]

Inversion formula: The index of any binary palindrome b = a(n) > 0 is n = palindromicIndex(b) = ((5-(-1)^m)/2 + Sum_{k=1..[m/2]} ([b/2^k] mod 2)/2^k)*2^[m/2], where [.] = floor(.) and m = [log_2(b)].

(End)

G.f.: g(x) = x^2 + 3x^3 + sum_{j=1..oo}( 3*2^j*(1-x^floor((j+1)/2))/(1-x)*x^((1/2)-floor((j+1)/2)) + f_j(x) - f_j(1/x))*x^(2*2^floor(j/2)+3*2^floor((j-1)/2)-(1/2)), where the f_j(x) are defined as follows:

f_1(x) = x^(1/2), and for j > 1,

f_j(x) = x^(1/2)*sum_{i=0..2^floor((j-1)/2)-1}((3+(1/2)*sum_{k=1..floor((j-1)/2)}(1-(-1)^floor(2i/2^k))*b(j,k))*x^i), where b(j,k) = 2^(floor((j-1)/2)-k)*((3+(-1)^j)*2^(2*k+1)+4) for k > 1, and b(j,1) = (2+(-1)^j)*2^(floor((j-1)/2)+1). - Hieronymus Fischer, Apr 04 2012

A044051(n) = (a(n)+1)/2 for n > 0. - Reinhard Zumkeller, Apr 20 2015

A145799(a(n)) = a(n). - Reinhard Zumkeller, Sep 24 2015

Sum_{n>=2} 1/a(n) = A244162. - Amiram Eldar, Oct 17 2020

Example

a(3) = 3, since 3 = 11_2 is the 3rd symmetric binary number;
a(6) = 9, since 9 = 1001_2 is the 6th symmetric binary number.

Maple

dmax:= 15; # to get all terms with at most dmax binary digits
revdigs:= proc(n)
  local L, Ln, i;
  L:= convert(n, base, 2);
  Ln:= nops(L);
  add(L[i]*2^(Ln-i), i=1..Ln);
end proc;
A:= {0, 1}:
for d from 2 to dmax do
  if d::even then
    A:= A union {seq(2^(d/2)*x + revdigs(x), x=2^(d/2-1)..2^(d/2)-1)}
  else
    m:= (d-1)/2;
    B:={seq(2^(m+1)*x + revdigs(x), x=2^(m-1)..2^m-1)};
    A:= A union B union map(`+`, B, 2^m)
  fi
od:
A;  # Robert Israel, Aug 17 2014

Mathematica

palQ[n_Integer, base_Integer] := Module[{idn=IntegerDigits[n, base]}, idn==Reverse[idn]]; Select[Range[1000], palQ[ #, 2]&]
Select[ Range[0, 1000], # == IntegerReverse[#, 2] &] (* Robert G. Wilson v, Feb 24 2018 *)
Select[Range[0, 1000], PalindromeQ[IntegerDigits[#, 2]]&] (* Jean-François Alcover, Mar 01 2018 *)

Prog

(PARI) for(n=0, 999, n-subst(Polrev(binary(n)), x, 2)||print1(n, ", ")) \\ Thomas Buchholz, Aug 16 2014
(PARI) for(n=0, 10^3, my(d=digits(n, 2)); if(d==Vecrev(d), print1(n, ", "))); \\ Joerg Arndt, Aug 17 2014
(PARI) is_A006995(n)=Vecrev(n=binary(n))==n \\ M. F. Hasler, Feb 23 2018
(PARI) A006995(n, m=logint(n, 2), c=1<<(m-1), a, d)={if(n>=3*c, a=n-3*c; d=2*c^2, a=n-2*c; n%2*c+d=c^2)+sum(k=1, m-2^(n<3*c), if(bittest(a, m-1-k), 1<<k+d>>k))+(n>2)} \\ Based on Fischer's smalltalk program. - M. F. Hasler, Feb 23 2018
(Magma) [n: n in [0..850] | Intseq(n, 2) eq Reverse(Intseq(n, 2))];  // Bruno Berselli, Aug 29 2011
(Haskell)
a006995 n = a006995_list !! (n-1)
a006995_list = 0 : filter ((== 1) . a178225) a005408_list
-- Reinhard Zumkeller, Oct 21 2011
(Smalltalk)
A006995
"Answer the n-th binary palindrome
(nonrecursive implementation)"
| m n a b c d k2 |
n := self.
n = 1 ifTrue: [^0].
n = 2 ifTrue: [^1].
m := n integerFloorLog: 2.
c := 2 raisedToInteger: m - 1.
n >= (3 * c)
  ifTrue:
   [a := n - (3 * c).
   d := 2 * c * c.
   b := d + 1.
   k2 := 1.
   1 to: m - 1
    do:
     [:k |
     k2 := 2 * k2.
     b := b + (a * k2 // c \\ 2 * (k2 + (d // k2)))]]
  ifFalse:
   [a := n - (2 * c).
   d := c * c.
   b := d + 1 + (n \\ 2 * c).
   k2 := 1.
   1 to: m - 2
    do:
     [:k |
     k2 := 2 * k2.
     b := b + (a * k2 // c \\ 2 * (k2 + (d // k2)))]].
^b // by Hieronymus Fischer, Feb 15 2013
(Sage)
def palgenbase2(): # generator of palindromes in base 2
    yield 0
    x, n, n2 = 1, 1, 2
    while True:
        for y in range(n, n2):
            s = format(y, 'b')
            yield int(s+s[-2::-1], 2)
        for y in range(n, n2):
            s = format(y, 'b')
            yield int(s+s[::-1], 2)
        x += 1
        n *= 2
        n2 *= 2 # Chai Wah Wu, Jan 07 2015
(Sage)
[n for n in (0..843) if Word(n.digits(2)).is_palindrome()] # Peter Luschny, Sep 13 2018
(Python)
from itertools import count, islice, product
def bin_pals(): # generator of binary palindromes in base 10
    yield from [0, 1]
    digits, midrange = 2, [[""], ["0", "1"]]
    for digits in count(2):
        for p in product("01", repeat=digits//2-1):
            left = "1"+"".join(p)
            for middle in midrange[digits%2]:
                yield int(left + middle + left[::-1], 2)
print(list(islice(bin_pals(), 58))) # Michael S. Branicky, Jan 09 2023
(Python)
def A006995(n):
    if n == 1: return 0
    a = 1<<(l:=n.bit_length()-2)
    m = a|(n&a-1)
    return (m<<l+1)+int(bin(m)[-1:1:-1]or'0', 2) if a&n else (m<<l)+int(bin(m)[-2:1:-1]or'0', 2) # Chai Wah Wu, Jun 10 2024

Crossrefs

See A057148 for the binary representations.

Cf. A178225, A005408, A164126, A154809 (complement).

Cf. A002113, A048700, A048701, A206913, A206914, A244162.

Even numbers that are not the sum of two terms: A241491, A261678, A262556.

Cf. A145799.

Primes: A016041 and A117697.

Cf. A000051 (a subsequence).

Keyword

nonn,base,easy,nice,hear

Author

N. J. A. Sloane, Robert G. Wilson v, Mira Bernstein, L. J. Upton

Extensions

Edited and extended by Hieronymus Fischer, Feb 21 2012

Edited by M. F. Hasler, Feb 23 2018

Status

approved

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,3

Comments

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)

Links

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)

Formula

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

Example

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)

Mathematica

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

Prog

(Haskell)
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
(Haskell)
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
(PARI) N=66; q='q+O('q^N); Vec( 1/((1-q)*eta(q^2)) ) \\ Joerg Arndt, Mar 11 2014

Crossrefs

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.

Keyword

nonn

Author

Clark Kimberling

Extensions

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

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

Status

approved

A007500 Primes whose reversal in base 10 is also prime (called "palindromic primes" by D. Wells, although that name usually refers to A002385). Also called reversible primes. (Formerly M0657)

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, 373, 383, 389, 701, 709, 727, 733, 739, 743, 751, 757, 761, 769, 787, 797, 907, 919, 929, 937, 941, 953, 967, 971, 983, 991, 1009, 1021

Offset

1,1

Comments

The numbers themselves need not be palindromes.

The range is a subset of the range of A071786. - Reinhard Zumkeller, Jul 06 2009

Number of terms less than 10^n: 4, 13, 56, 260, 1759, 11297, 82439, 618017, 4815213, 38434593, ..., . - Robert G. Wilson v, Jan 08 2015

References

Roozbeh Hazrat, Mathematica: A Problem-Centered Approach, Springer 2010, pp. 39, 131-132

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

D. Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, 134.

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

Cécile Dartyge, Bruno Martin, Joël Rivat, Igor E. Shparlinski, and Cathy Swaenepoel, Reversible primes, arXiv:2309.11380 [math.NT], 2023. See p. 3.

Maple

revdigs:= proc(n)
local L, nL, i;
L:= convert(n, base, 10);
nL:= nops(L);
add(L[i]*10^(nL-i), i=1..nL);
end:
Primes:= select(isprime, {2, seq(2*i+1, i=1..5*10^5)}):
Primes intersect map(revdigs, Primes); # Robert Israel, Aug 14 2014

Mathematica

Select[ Prime[ Range[ 168 ] ], PrimeQ[ FromDigits[ Reverse[ IntegerDigits[ # ] ] ] ]& ] (* Zak Seidov, corrected by T. D. Noe *)
Select[Prime[Range[1000]], PrimeQ[IntegerReverse[#]]&] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Aug 15 2016 *)

Prog

(Magma) [ p: p in PrimesUpTo(1030) | IsPrime(Seqint(Reverse(Intseq(p)))) ];  // Bruno Berselli, Jul 08 2011
(Haskell)
a007500 n = a007500_list !! (n-1)
a007500_list = filter ((== 1) . a010051 . a004086) a000040_list
-- Reinhard Zumkeller, Oct 14 2011
(PARI) is_A007500(n)={ isprime(n) & is_A095179(n)} \\ M. F. Hasler, Jan 13 2012
(Python)
from sympy import prime, isprime
A007500 = [prime(n) for n in range(1, 10**6) if isprime(int(str(prime(n))[::-1]))] # Chai Wah Wu, Aug 14 2014

Crossrefs

Cf. A006567, A007628.

Cf. A002385 (primes that are palindromes in base 10).

Equals A002385 union A006567.

Complement of A076056 with respect to A000040. [From Reinhard Zumkeller, Jul 06 2009]

Cf. A004086, A010051, A000040.

Keyword

base,nonn,nice

Author

N. J. A. Sloane, Robert G. Wilson v

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Oct 31 2000

Added further terms to the sequence Avik Roy (avik_3.1416(AT)yahoo.co.in), Jan 16 2009. Checked by N. J. A. Sloane, Jan 20 2009.

Third reference added by Harvey P. Dale, Oct 17 2011

Status

approved

A261423 Largest palindrome <= n.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 77, 77

Offset

0,3

Comments

Might be called the palindromic floor function.

Let P(n) = n with the second half of its digits replaced by the first half of the digits in reverse order. If P(n) <= n, then a(n) = P(n), else if n=10^k then a(n) = n-1, else a(n) = P(n-10^floor(d/2)), where d is the number of digits of n. - M. F. Hasler, Sep 08 2015

The largest differences of n - a(n) occur for n = m*R(2k) - 1, where 1 <= m <= 9 and R(k)=(10^k-1)/9. In this case, n - a(n) = 1.1*10^k - 1. - M. F. Hasler, Sep 05 2018

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, Palindromic Number

Wikipedia, Palindromic number

Index entries for sequences related to palindromes

Formula

n - a(n) < 1.1*10^floor(d/2), where d = floor(log_10(n)) + 1 is the number of digits of n. - M. F. Hasler, Sep 05 2018

Maple

# P has list of palindromes
palfloor:=proc(n) global P; local i;
for i from 1 to nops(P) do
   if P[i]=n then return(n); fi;
   if P[i]>n then return(P[i-1]); fi;
od:
end;

Mathematica

palQ[n_] := Block[{d = IntegerDigits@ n}, d == Reverse@ d]; Table[k = n;
While[Nand[palQ@ k, k > -1], k--]; k, {n, 0, 78}] (* Michael De Vlieger, Sep 09 2015 *)

Prog

(PARI) A261423(n, d=digits(n), m=sum(k=1, #d\2, d[k]*10^(k-1)))={if( n%10^(#d\2)<m, n==10^valuation(n, 10)&&return(n-1); d=digits(n-=10^(#d\2) /*#digits may decrease!*/); sum(k=1, #d\2, d[k]*10^(k-1)), m)+n-n%10^(#d\2)} \\ M. F. Hasler, Sep 08 2015, minor edit on Sep 05 2018
(Haskell)
a261423 n = a261423_list !! n
a261423_list = tail a261914_list  -- Reinhard Zumkeller, Sep 16 2015
(Python)
def P(n):
    s = str(n); h = s[:(len(s)+1)//2]; return int(h + h[-1-len(s)%2::-1])
def a(n):
    s = str(n)
    if s == '1'+'0'*(len(s)-1) and n > 1: return n - 1
    Pn = P(n)
    return Pn if Pn <= n else P(n - 10**(len(s)//2))
print([a(n) for n in range(79)]) # Michael S. Branicky, Jun 25 2021

Crossrefs

Cf. A002113, A261424, A261914 (previous palindrome).

Cf. A262038.

Sequences related to palindromic floor and ceiling: A175298, A206913, A206914, A261423, A262038, and the large block of consecutive sequences beginning at A265509.

A262257(n) = Levenshtein distance between n and a(n). - Reinhard Zumkeller, Sep 16 2015

Keyword

nonn,base

Author

N. J. A. Sloane, Aug 28 2015

Status

approved

A262038 Least palindrome >= n.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 11, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77

Offset

0,3

Comments

Could be called nextpalindrome() in analogy to the nextprime() function A007918. As for the latter (A151800), there is the variant "next strictly larger palindrome" which equals a(n+1), and thus differs from a(n) iff n is a palindrome; see PARI code.

Might also be called palindromic ceiling function in analogy to the name "palindromic floor" proposed for A261423.

Links

M. F. Hasler, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, Palindromic Number

Wikipedia, Palindromic number

Index entries for sequences related to palindromes

Mathematica

palQ[n_] := Block[{d = IntegerDigits@ n}, d == Reverse@ d]; Table[k = n; While[! palQ@ k, k++]; k, {n, 0, 80}] (* Michael De Vlieger, Sep 09 2015 *)

Prog

(PARI) {A262038(n, d=digits(n), p(d)=sum(i=1, #d\2, (10^(i-1)+10^(#d-i))*d[i], if(bittest(#d, 0), 10^(#d\2)*d[#d\2+1])))= for(i=(#d+3)\2, #d, d[i]>d[#d+1-i]&&break; (d[i]<d[#d+1-i]||i==#d)&&return(p(d))); n<10&&return(n); forstep(i=(#d+1)\2, 1, -1, d[i]++>9||return(p(d)); d[i]=0); 10^#d+1} \\ For a function "next strictly larger palindrome", delete the i==#d and n<10... part. - M. F. Hasler, Sep 09 2015
(Haskell)
a262038 n = a262038_list !! n
a262038_list = f 0 a002113_list where
   f n ps'@(p:ps) = p : f (n + 1) (if p > n then ps' else ps)
-- Reinhard Zumkeller, Sep 16 2015
(Python)
def A262038(n):
    sl = len(str(n))
    l = sl>>1
    if sl&1:
        w = 10**l
        n2 = w*10
        for y in range(n//(10**l), n2):
            k, m = y//10, 0
            while k >= 10:
                k, r = divmod(k, 10)
                m = 10*m + r
            z = y*w + 10*m + k
            if z >= n:
                return z
    else:
        w = 10**(l-1)
        n2 = w*10
        for y in range(n//(10**l), n2):
            k, m = y, 0
            while k >= 10:
                k, r = divmod(k, 10)
                m = 10*m + r
            z = y*n2 + 10*m + k
            if z >= n:
                return z # Chai Wah Wu, Sep 14 2022

Crossrefs

Cf. A002113, A261423, A262037.

Sequences related to palindromic floor and ceiling: A175298, A206913, A206914, A261423, A262038, and the large block of consecutive sequences beginning at A265509.

Keyword

nonn,base

Author

M. F. Hasler, Sep 08 2015

Status

approved

A206913 Greatest binary palindrome <= n; the binary palindrome floor function.

0, 1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 9, 9, 9, 9, 15, 15, 17, 17, 17, 17, 21, 21, 21, 21, 21, 21, 27, 27, 27, 27, 31, 31, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 45, 45, 45, 45, 45, 45, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 63, 63, 65, 65, 65, 65

Offset

0,4

Comments

Also the greatest binary palindrome < n + 1;

For n > 0, a(n-1) is the greatest binary palindrome < n.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Formula

Let n > 2, p = 1 + 2*floor((n-1)/2), m = floor(log_2(p)), q = floor((m+1)/2), s = floor(log_2(p-2^q)),

F(x, r) = floor(x/2^q)*2^q + Sum_{k = 0...q - 1} (floor(x/2^(r-k)) mod 2)*2^k;

If F(p, m) <= n then a(n) = F(p, m), otherwise a(n) = F(p-2^q, s).

By definition: F(p, m) = floor(p/2^q)*2^q + A030101(p) mod 2^q; also: F(p-2^q, s) = floor((p-2^q)/2^q)*2^q + A030101(p-2^q) mod 2^q; [Edited and corrected by Hieronymus Fischer, Sep 08 2018]

a(n) = A006995(A206915(n));

a(n) = A006995(A206915(A206914(n+1))-1);

a(n) = A006995(A206916(A206914(n+1))-1).

Example

a(0) = 0 since 0 is the greatest binary palindrome <= 0;
a(1) = 1 since 1 is the greatest binary palindrome <= 1;
a(2) = 1 since 1 is the greatest binary palindrome <= 2;
a(3) = 3 since 3 is the greatest binary palindrome <= 3.

Prog

(Haskell)
a206913 n = last $ takeWhile (<= n) a006995_list
-- Reinhard Zumkeller, Feb 27 2012

Crossrefs

Cf. A006995, A206915, A206920, A030301.

Sequences related to palindromic floor and ceiling: A175298, A206913, A206914, A261423, A262038, and the large block of consecutive sequences beginning at A265509.

Keyword

nonn,base

Author

Hieronymus Fischer, Feb 13 2012

Status

approved

A175298 Smallest number >=n whose binary representation is palindromic and has a 1 whenever the binary representation of n has a 1.

0, 1, 3, 3, 5, 5, 7, 7, 9, 9, 15, 15, 15, 15, 15, 15, 17, 17, 27, 27, 21, 21, 31, 31, 27, 27, 27, 27, 31, 31, 31, 31, 33, 33, 51, 51, 45, 45, 63, 63, 45, 45, 63, 63, 45, 45, 63, 63, 51, 51, 51, 51, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 65, 65, 99, 99, 85, 85, 119, 119, 73

Offset

0,3

Comments

Old name: "Convert n to binary. OR each respective digit of binary n and binary A030101(n), where A030101(n) is the reversal of the order of the digits in the binary representation of n (given in decimal). a(n) is the decimal value of the result."

By "respective" digits of binary n and binary A030101(n), the rightmost digit of A030101(n) ( which is a 1) is OR'ed with the rightmost digit of n. A030101(n) is represented with the appropriate number of leading 0's.

This is the binary next-palindrome function, the base-2 analog of A262038. - N. J. A. Sloane, Dec 08 2015

Links

Alois P. Heinz, Table of n, a(n) for n = 0..16383

Example

20 in binary is 10100. The reversal of the binary digits is 00101. So, from leftmost to rightmost respective digits, we OR 10100 and 00101: 1 OR 0 = 1. 0 OR 0 = 0. 1 OR 1 = 1. 0 OR 0 = 0. And 0 OR 1 = 1. So, 10100 OR 00101 is 10101, which is 21 in decimal. So a(20) = 21.

Mathematica

Table[f = IntegerDigits[x, 2]; f = f + Reverse[f]; FromDigits[ Table[If[Positive[f[[r]]], 1, 0], {r, 1, Length[f]}], 2], {x, STARTPOINT, ENDPOINT}] (* Dylan Hamilton, Oct 15 2010 *)
f[n_] := Block[{id = IntegerDigits[n, 2]}, FromDigits[ BitOr[ id, Reverse@id], 2]]; Array[f, 72] (* Robert G. Wilson v, Nov 07 2010 *)

Crossrefs

Cf. A006995, A030101, A175297, A262038.

Sequences related to palindromic floor and ceiling: A175298, A206913, A206914, A261423, A262038, and the large block of consecutive sequences beginning at A265509.

Keyword

base,nonn

Author

Leroy Quet, Mar 24 2010

Extensions

Extended, with redundant initial entries included, by Dylan Hamilton, Oct 15 2010

Edited with new name and offset by N. J. A. Sloane, Dec 08 2015

Status

approved

A206914 Least binary palindrome >= n; the binary palindrome ceiling function.

0, 1, 3, 3, 5, 5, 7, 7, 9, 9, 15, 15, 15, 15, 15, 15, 17, 17, 21, 21, 21, 21, 27, 27, 27, 27, 27, 27, 31, 31, 31, 31, 33, 33, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 51, 51, 51, 51, 51, 51, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 65, 65, 73, 73

Offset

0,3

Comments

For n > 0 also the least binary palindrome > n - 1;

a(n+1) is the least binary palindrome > n

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Formula

a(n) = A006995(A206916(n));

a(n) = A006995(A206916(A206913(n-1))+1);

a(n) = A006995(A206915(A206913(n-1))+1);

Example

a(0) = 0 since 0 is the least binary palindrome >= 0;
a(1) = 1 since 1 is the least binary palindrome >= 1;
a(2) = 3 since 3 is the least binary palindrome >= 2;
a(5) = 5 since 5 is the least binary palindrome >= 5;

Prog

(Haskell)
a206914 n = head $ dropWhile (< n) a006995_list
-- Reinhard Zumkeller, Feb 27 2012

Crossrefs

Cf. A206915, A206920, A006995.

Sequences related to palindromic floor and ceiling: A175298, A206913, A206914, A261423, A262038, and the large block of consecutive sequences beginning at A265509.

Keyword

nonn,base

Author

Hieronymus Fischer, Feb 15 2012

Status

approved