cp's OEIS Frontend

A293701 a(n) is the length of the longest palindromic subsequence in the first n terms of A293700.

%I A293701 #52 Oct 08 2022 00:01:55
%S A293701 1,1,3,3,5,5,7,7,9,9,11,11,13,13,15,15,17,17,17,17,17,17,17,17,17,17,
%T A293701 17,17,17,17,17,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,46,46,46,
%U A293701 46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,47,49
%N A293701 a(n) is the length of the longest palindromic subsequence in the first n terms of A293700.
%C A293701 If a(n + 1) > a(n) for some n, then A293700(n + 1) is in the longest palindrome. So to find a(n + 1) it suffices to check if A293700 is in the palindrome, which must be at least of length a(n). - _David A. Corneth_, Nov 25 2017
%C A293701 At points where a(n) = n, the whole sequence is a palindrome. For example at n=9105, the length of the longest palindrome a(9105) is 9105 (see A294923).
%H A293701 Antti Karttunen, <a href="/A293701/b293701.txt">Table of n, a(n) for n = 1..10000</a> (computed with the given Scheme-program from the b-file of A293700 provided by Robert Israel)
%H A293701 V.J. Pohjola, <a href="https://palindromesdotblog.files.wordpress.com/2017/12/lenpalsp-1-100.pdf">Line plot of n, a(n) for n=1...100</a>
%H A293701 V.J. Pohjola, <a href="https://palindromesdotblog.files.wordpress.com/2017/12/lenpalsp-1-1400.pdf">Line plot of n, a(n)  for n=1...1400</a>
%H A293701 V.J. Pohjola, <a href="https://palindromesdotblog.files.wordpress.com/2017/12/lenpalsp-1-10000.pdf">Line plot of n, a(n)  for n=1...10000</a>
%e A293701 For n = 1, roots = 1, 4; first differences = 3; longest palindrome = 3; a(n) = 1.
%e A293701 For n = 2, roots = 1, 4, 23; first differences = 3, 19; longest palindrome = 3; a(n) = 1.
%e A293701 For n = 3, roots = 1, 4, 23, 26; first differences = 3, 19, 3; longest palindrome = 3, 19, 3; a(n) = 3.
%e A293701 For n = 33, roots = 1, 4, 23, 26, 45, 48, 67, 70, 89, 92, 111, 114, 133, 136, 155, 158, 177, 180, 183, 199, 202, 205, 221, 224, 227, 243, 246, 249, 265, 268, 271, 290, 293, 312; first differences = 3, 19, 3, 19, 3, 19, 3, 19, 3, 19, 3, 19, 3, 19, 3, 19, 3, 3, 16, 3, 3, 16, 3, 3, 16, 3, 3, 16, 3, 3, 19, 3, 19; longest palindrome = 19, 3, 19, 3, 3, 16, 3, 3, 16, 3, 3, 16, 3, 3, 16, 3, 3, 19, 3, 19; a(n) = 20.
%t A293701 rootsp = Flatten[Position[Table[Floor[Tan[i]], {i, 1, 10^4}], 1]];
%t A293701 lrootsp = Length[rootsp];
%t A293701 difp = Differences[rootsp];
%t A293701 ldp = Length[difp];
%t A293701 nmax = 200; palsp = {}; lenpalsp = {0};
%t A293701 Do[diffip = difp[[1 ;; n]]; lendiffip = Length[diffip];
%t A293701   pmax = n - Last[lenpalsp];
%t A293701   t = Table[difp[[p ;; n]], {p, 1, pmax}];
%t A293701   sp = Flatten[Select[t, # == Reverse[#] &]];
%t A293701   If[sp == {},
%t A293701    AppendTo[palsp, Last[palsp]] && AppendTo[lenpalsp, Last[lenpalsp]],
%t A293701    AppendTo[palsp, sp] && AppendTo[lenpalsp, Length[Flatten[sp]]]], {n, 1, nmax}];
%t A293701 Drop[lenpalsp,1](*a(n)=Drop[lenpalsp,1][[n]]*)
%o A293701 (PARI) firstsols(n) = {my(res = vector(n), i = 0, pi = [Pi, Pi], sols = [atan(1), atan(2)]); while(1, for(j = ceil(sols[1]), floor(sols[2]), i++; if(i>n, return(res)); res[i] = j); sols+=[Pi(), Pi()])} \\ A293698
%o A293701 diff(v) = vector(#v-1,i,v[i+1]-v[i]);
%o A293701 first(n) = {my(res = vector(n), m = 0, check = diff(firstsols(n+1))); for(i=1, n, for(j = 1, i - m, if(ispalindrome(check, j, i), m = i - j + 1; next(1))); res[i] = m); res}
%o A293701 ispalindrome(v, {llim = 1}, {ulim = #v}) = {for(i=0, (ulim - llim) \ 2, if(v[llim + i]!=v[ulim - i], return(0))); 1} \\ _David A. Corneth_, Nov 25 2017
%o A293701 (Scheme)
%o A293701 ;; This uses memoization-macro definec and assumes also that A293700 is available:
%o A293701 (definec (A293701 n) (if (= 1 n) n (let outloop ((k n)) (cond ((<= k (A293701 (- n 1))) (A293701 (- n 1))) (else (let inloop ((i n)) (let ((low-ind (+ 1 (- n k) (- n i)))) (cond ((< i low-ind) (max k (A293701 (- n 1)))) ((not (= (A293700 i) (A293700 low-ind))) (outloop (- k 1))) (else (inloop (- i 1)))))))))))
%o A293701 ;; _Antti Karttunen_, Nov 25 2017
%Y A293701 Cf. A293698, A293699, A293700, A293702, A293703, A293704, A293705, A293706, A293751.
%K A293701 nonn,easy
%O A293701 1,3
%A A293701 _V.J. Pohjola_, Oct 16 2017