login
A284553
Prime factorization representation of Stern polynomials B(n,x) with only the even powers of x present: a(n) = A247503(A260443(n)).
4
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,2
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.
LINKS
S. Klavzar, U. Milutinovic and C. Petr, Stern polynomials, Adv. Appl. Math. 39 (2007) 86-95.
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.]
EXAMPLE
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
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 *)
PROG
(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
(Scheme) (define (A284553 n) (A247503 (A260443 n)))
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Mar 29 2017
STATUS
approved