A284553 Prime factorization representation of Stern polynomials B(n,x) with only the even powers of x present: a(n) = A247503(A260443(n)).

1, 2, 1, 2, 5, 2, 5, 10, 1, 10, 25, 10, 5, 50, 5, 10, 11, 10, 25, 250, 5, 250, 125, 50, 11, 250, 25, 250, 55, 50, 55, 110, 1, 110, 275, 250, 55, 6250, 125, 1250, 121, 1250, 625, 31250, 55, 6250, 1375, 550, 11, 2750, 275, 6250, 605, 6250, 1375, 13750, 11, 2750, 3025, 2750, 55, 6050, 55, 110, 17, 110, 275, 30250, 55, 68750, 15125, 13750, 121

Offset: 0

Author

Antti Karttunen, Mar 29 2017

Keywords

• nonn

Comments

a(n) = Prime factorization representation of Stern polynomials B(n,x) where the coefficients of odd powers of x are replaced by zeros. In other words, only the constant term and other terms with even powers of x are present. See the examples.

Proof that A001222(a(1+n)) matches Ralf Stephan's formula for A000360(n): Consider functions A001222(a(n)) and A001222(A284554(n)) (= A284556(n)). They can be reduced to the following mutual recurrence pair: b(0) = 0, b(1) = 1, b(2n) = c(n), b(2n+1) = b(n) + b(n+1) and c(0) = c(1) = 0, c(2n) = b(n), c(2n+1) = c(n) + c(n+1). From the definitions it follows that the difference b(n) - c(n) for even n is b(2n) - c(2n) = -(b(n) - c(n)), and for odd n, b(2n+1) - c(2n+1) = (b(n)+b(n+1))-(c(n)+c(n+1)) = (b(n)-c(n)) + (b(n+1)-c(n+1)). Then by induction, if we assume that for 3n, 3n+1, 3n+2, ..., 6n, the value of difference b(n)-c(n) is always [0, +1, -1; repeated], it follows that from 6n to 12n the differences are [0, +1, -1; 0, +1, -1; repeated], which proves that b(n) - c(n) = A102283(n). As an implication, recurrence b can be defined without referring to c as: b(0) = 0, b(1) = 1, b(2n) = b(n) - A102283(n), b(2n+1) = b(n)+b(n+1), and this is equal to Ralf Stephan's Oct 05 2003 formula for A000360, but shifted once right, with prepended zero.

Examples

			n A260443(n)                      Stern            With odd powers
             prime factorization  polynomial       of x cleared  -> a(n)
------------------------------------------------------------------------
0       1    (empty)              B_0(x) = 0                    0  |  1
1       2    p_1                  B_1(x) = 1                    1  |  2
2       3    p_2                  B_2(x) = x                    0  |  1
3       6    p_2 * p_1            B_3(x) = x + 1                1  |  2
4       5    p_3                  B_4(x) = x^2                x^2  |  5
5      18    p_2^2 * p_1          B_5(x) = 2x + 1               1  |  2
6      15    p_3 * p_2            B_6(x) = x^2 + x            x^2  |  5
7      30    p_3 * p_2 * p_1      B_7(x) = x^2 + x + 1    x^2 + 1  | 10
8       7    p_4                  B_8(x) = x^3                  0  |  1
9      90    p_3 * p_2^2 * p_1    B_9(x) = x^2 + 2x + 1   x^2 + 1  | 10
10     75    p_3^2 * p_2          B_10(x) = 2x^2 + x         2x^2  | 25
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8192
• S. Klavzar, U. Milutinovic and C. Petr, Stern polynomials, Adv. Appl. Math. 39 (2007) 86-95.

Crossrefs

Cf. A000360, A001222, A003961, A064989, A102283, A247503, A260443, A284554, A284556, A284563 (odd bisection).

Programs

Mathematica

a[n_] := a[n] = Which[n < 2, n + 1, EvenQ@ n, Times @@ Map[#1^#2 & @@ # &, FactorInteger[#] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[# == 1] &@ a[n/2], True, a[#] a[# + 1] &[(n - 1)/2]]; Table[Times @@ (FactorInteger[#] /. {p_, e_} /; e > 0 :> (p^Mod[PrimePi@ p, 2])^e) &@ a@ n, {n, 0, 72}] (* Michael De Vlieger, Apr 05 2017 *)

PARI

A003961(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); }; \\ From Michel Marcus
A260443(n) = if(n<2, n+1, if(n%2, A260443(n\2)*A260443(n\2+1), A003961(A260443(n\2)))); \\ Cf. Charles R Greathouse IV's code for "ps" in A186891 and A277013.
A247503(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 2] *= (primepi(f[i, 1]) % 2); ); factorback(f); } \\ After Michel Marcus
A284553(n) = A247503(A260443(n));

Scheme

(define (A284553 n) (A247503 (A260443 n)))

Formula

a(0) = 1, a(1) = 2, a(2n) = A003961(A284554(n)), a(2n+1) = a(n)*a(n+1).

Other identities. For all n >= 0:

a(n) = A247503(A260443(n)).

a(n) = A260443(n) / A284554(n).

a(n) = A064989(A284554(2n)).

A001222(a(1+n)) = A000360(n). [Proof in Comments section.]