A260443 Prime factorization representation of Stern polynomials: a(0) = 1, a(1) = 2, a(2n) = A003961(a(n)), a(2n+1) = a(n)*a(n+1).

1, 2, 3, 6, 5, 18, 15, 30, 7, 90, 75, 270, 35, 450, 105, 210, 11, 630, 525, 6750, 245, 20250, 2625, 9450, 77, 15750, 3675, 47250, 385, 22050, 1155, 2310, 13, 6930, 5775, 330750, 2695, 3543750, 128625, 1653750, 847, 4961250, 643125, 53156250, 18865, 24806250, 202125, 727650, 143, 1212750, 282975, 57881250, 29645, 173643750, 1414875, 18191250, 1001

Offset: 0

Author

Antti Karttunen, Jul 28 2015

Keywords

• nonn
• look

Comments

The exponents in the prime factorization of term a(n) give the coefficients of the n-th Stern polynomial. See A125184 and the examples.

None of the terms have prime gaps in their factorization, i.e., all can be found in A073491.

Contains neither perfect squares nor prime powers with exponent > 1. A277701 gives the positions of the terms that are 2*square. - Antti Karttunen, Oct 27 2016

Many of the derived sequences (like A002487) have similar "Fir forest" or "Gaudian cathedrals" style scatter plot. - Antti Karttunen, Mar 21 2017

Examples

			n    a(n)   prime factorization    Stern polynomial
------------------------------------------------------------
0       1   (empty)                B_0(x) = 0
1       2   p_1                    B_1(x) = 1
2       3   p_2                    B_2(x) = x
3       6   p_2 * p_1              B_3(x) = x + 1
4       5   p_3                    B_4(x) = x^2
5      18   p_2^2 * p_1            B_5(x) = 2x + 1
6      15   p_3 * p_2              B_6(x) = x^2 + x
7      30   p_3 * p_2 * p_1        B_7(x) = x^2 + x + 1
8       7   p_4                    B_8(x) = x^3
9      90   p_3 * p_2^2 * p_1      B_9(x) = x^2 + 2x + 1
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..4096 (first 1025 terms from Antti Karttunen)

Crossrefs

Same sequence sorted into ascending order: A260442.

Cf. A000040, A000079, A000225, A001222, A002487, A003415, A003961, A005811, A007949, A046523, A056239, A073491, A090880, A097249, A101979, A125184, A178590, A186891, A206284, A277314, A277315, A277325, A277326, A277329, A277330, A277701, A277705, A277899, A278243, A278530, A278544, A284010, A284011.

Cf. also A048675, A277333 (left inverses).

Cf. A277323, A277324 (bisections), A277200 (even terms sorted), A277197 (first differences), A277198.

Cf. A277316 (values at primes), A277318.

Cf. A023758 (positions of squarefree terms), A101082 (of terms not squarefree), A277702 (positions of records), A277703 (their values).

Cf. A283992, A283993 (number of irreducible, reducible polynomials in range 1 .. n).

Cf. also A206296 (Fibonacci polynomials similarly represented).

Programs

Maple

b:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
a:= proc(n) option remember; `if`(n<2, n+1,
      `if`(irem(n, 2, 'h')=0, b(a(h)), a(h)*a(n-h)))
    end:
seq(a(n), n=0..56);  # Alois P. Heinz, Jul 04 2024

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[a@ n, {n, 0, 56}] (* 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)))); \\ After Charles R Greathouse IV's code for "ps" in A186891.
\\ Antti Karttunen, Oct 11 2016

Python

from sympy import factorint, prime, primepi
from functools import reduce
from operator import mul
def a003961(n):
    F = factorint(n)
    return 1 if n==1 else reduce(mul, (prime(primepi(i) + 1)**F[i] for i in F))
def a(n): return n + 1 if n<2 else a003961(a(n//2)) if n%2==0 else a((n - 1)//2)*a((n + 1)//2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 21 2017

Scheme

;; Uses memoization-macro definec:
(definec (A260443 n) (cond ((<= n 1) (+ 1 n)) ((even? n) (A003961 (A260443 (/ n 2)))) (else (* (A260443 (/ (- n 1) 2)) (A260443 (/ (+ n 1) 2))))))
;; A more standalone version added Oct 10 2016, requiring only an implementation of A000040 and the memoization-macro definec:
(define (A260443 n) (product_primes_to_kth_powers (A260443as_coeff_list n)))
(define (product_primes_to_kth_powers nums) (let loop ((p 1) (nums nums) (i 1)) (cond ((null? nums) p) (else (loop (* p (expt (A000040 i) (car nums))) (cdr nums) (+ 1 i))))))
(definec (A260443as_coeff_list n) (cond ((zero? n) (list)) ((= 1 n) (list 1)) ((even? n) (cons 0 (A260443as_coeff_list (/ n 2)))) (else (add_two_lists (A260443as_coeff_list (/ (- n 1) 2)) (A260443as_coeff_list (/ (+ n 1) 2))))))
(define (add_two_lists nums1 nums2) (let ((len1 (length nums1)) (len2 (length nums2))) (cond ((< len1 len2) (add_two_lists nums2 nums1)) (else (map + nums1 (append nums2 (make-list (- len1 len2) 0)))))))

Formula

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

Other identities. For all n >= 0:

A001221(a(n)) = A277314(n). [#nonzero coefficients in each polynomial.]

A001222(a(n)) = A002487(n). [When each polynomial is evaluated at x=1.]

A048675(a(n)) = n. [at x=2.]

A090880(a(n)) = A178590(n). [at x=3.]

A248663(a(n)) = A264977(n). [at x=2 over the field GF(2).]

A276075(a(n)) = A276081(n). ["at factorials".]

A156552(a(n)) = A277020(n). [Converted to "unary-binary" encoding.]

A051903(a(n)) = A277315(n). [Maximal coefficient.]

A277322(a(n)) = A277013(n). [Number of irreducible polynomial factors.]

A005361(a(n)) = A277325(n). [Product of nonzero coefficients.]

A072411(a(n)) = A277326(n). [And their LCM.]

A007913(a(n)) = A277330(n). [The squarefree part.]

A000005(a(n)) = A277705(n). [Number of divisors.]

A046523(a(n)) = A278243(n). [Filter-sequence.]

A284010(a(n)) = A284011(n). [True for n > 1. Another filter-sequence.]

A003415(a(n)) = A278544(n). [Arithmetic derivative.]

A056239(a(n)) = A278530(n). [Weighted sum of coefficients.]

A097249(a(n)) = A277899(n).

a(A000079(n)) = A000040(n+1).

a(A000225(n)) = A002110(n).

a(A000051(n)) = 3*A002110(n).

For n >= 1, a(A000918(n)) = A070826(n).

A007949(a(n)) is the interleaving of A000035 and A005811, probably A101979.

A061395(a(n)) = A277329(n).

Also, for all n >= 1:

A055396(a(n)) = A001511(n).

A252735(a(n)) = A061395(a(n)) - 1 = A057526(n).

a(A000040(n)) = A277316(n).

a(A186891(1+n)) = A277318(n). [Subsequence for irreducible polynomials].

Extensions

More linking formulas added by Antti Karttunen, Mar 21 2017