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
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.
FORMULA
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Mar 29 2017
STATUS
approved