A293701 - OEIS

%I #52 Oct 08 2022 00:01:55

%S 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 17,17,17,17,17,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,46,46,46,

%U 46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,47,49

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

%C 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 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 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 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 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 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 For n = 1, roots = 1, 4; first differences = 3; longest palindrome = 3; a(n) = 1.

%e For n = 2, roots = 1, 4, 23; first differences = 3, 19; longest palindrome = 3; a(n) = 1.

%e For n = 3, roots = 1, 4, 23, 26; first differences = 3, 19, 3; longest palindrome = 3, 19, 3; a(n) = 3.

%e 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 rootsp = Flatten[Position[Table[Floor[Tan[i]], {i, 1, 10^4}], 1]];

%t lrootsp = Length[rootsp];

%t difp = Differences[rootsp];

%t ldp = Length[difp];

%t nmax = 200; palsp = {}; lenpalsp = {0};

%t Do[diffip = difp[[1 ;; n]]; lendiffip = Length[diffip];

%t   pmax = n - Last[lenpalsp];

%t   t = Table[difp[[p ;; n]], {p, 1, pmax}];

%t   sp = Flatten[Select[t, # == Reverse[#] &]];

%t   If[sp == {},

%t    AppendTo[palsp, Last[palsp]] && AppendTo[lenpalsp, Last[lenpalsp]],

%t    AppendTo[palsp, sp] && AppendTo[lenpalsp, Length[Flatten[sp]]]], {n, 1, nmax}];

%t Drop[lenpalsp,1](*a(n)=Drop[lenpalsp,1][[n]]*)

%o (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 diff(v) = vector(#v-1,i,v[i+1]-v[i]);

%o 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 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 (Scheme)

%o ;; This uses memoization-macro definec and assumes also that A293700 is available:

%o (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 ;; _Antti Karttunen_, Nov 25 2017

%Y Cf. A293698, A293699, A293700, A293702, A293703, A293704, A293705, A293706, A293751.

%K nonn,easy

%O 1,3

%A _V.J. Pohjola_, Oct 16 2017