cp's OEIS Frontend

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).

%I A260443 #105 Jul 04 2024 05:02:20
%S A260443 1,2,3,6,5,18,15,30,7,90,75,270,35,450,105,210,11,630,525,6750,245,
%T A260443 20250,2625,9450,77,15750,3675,47250,385,22050,1155,2310,13,6930,5775,
%U A260443 330750,2695,3543750,128625,1653750,847,4961250,643125,53156250,18865,24806250,202125,727650,143,1212750,282975,57881250,29645,173643750,1414875,18191250,1001
%N 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).
%C A260443 The exponents in the prime factorization of term a(n) give the coefficients of the n-th Stern polynomial. See A125184 and the examples.
%C A260443 None of the terms have prime gaps in their factorization, i.e., all can be found in A073491.
%C A260443 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
%C A260443 Many of the derived sequences (like A002487) have similar "Fir forest" or "Gaudian cathedrals" style scatter plot. - _Antti Karttunen_, Mar 21 2017
%H A260443 Alois P. Heinz, <a href="/A260443/b260443.txt">Table of n, a(n) for n = 0..4096</a> (first 1025 terms from Antti Karttunen)
%F A260443 a(0) = 1, a(1) = 2, a(2n) = A003961(a(n)), a(2n+1) = a(n)*a(n+1).
%F A260443 Other identities. For all n >= 0:
%F A260443 A001221(a(n)) = A277314(n). [#nonzero coefficients in each polynomial.]
%F A260443 A001222(a(n)) = A002487(n). [When each polynomial is evaluated at x=1.]
%F A260443 A048675(a(n)) = n.          [at x=2.]
%F A260443 A090880(a(n)) = A178590(n). [at x=3.]
%F A260443 A248663(a(n)) = A264977(n). [at x=2 over the field GF(2).]
%F A260443 A276075(a(n)) = A276081(n). ["at factorials".]
%F A260443 A156552(a(n)) = A277020(n). [Converted to "unary-binary" encoding.]
%F A260443 A051903(a(n)) = A277315(n). [Maximal coefficient.]
%F A260443 A277322(a(n)) = A277013(n). [Number of irreducible polynomial factors.]
%F A260443 A005361(a(n)) = A277325(n). [Product of nonzero coefficients.]
%F A260443 A072411(a(n)) = A277326(n). [And their LCM.]
%F A260443 A007913(a(n)) = A277330(n). [The squarefree part.]
%F A260443 A000005(a(n)) = A277705(n). [Number of divisors.]
%F A260443 A046523(a(n)) = A278243(n). [Filter-sequence.]
%F A260443 A284010(a(n)) = A284011(n). [True for n > 1. Another filter-sequence.]
%F A260443 A003415(a(n)) = A278544(n). [Arithmetic derivative.]
%F A260443 A056239(a(n)) = A278530(n). [Weighted sum of coefficients.]
%F A260443 A097249(a(n)) = A277899(n).
%F A260443 a(A000079(n)) = A000040(n+1).
%F A260443 a(A000225(n)) = A002110(n).
%F A260443 a(A000051(n)) = 3*A002110(n).
%F A260443 For n >= 1, a(A000918(n)) = A070826(n).
%F A260443 A007949(a(n)) is the interleaving of A000035 and A005811, probably A101979.
%F A260443 A061395(a(n)) = A277329(n).
%F A260443 Also, for all n >= 1:
%F A260443 A055396(a(n)) = A001511(n).
%F A260443 A252735(a(n)) = A061395(a(n)) - 1 = A057526(n).
%F A260443 a(A000040(n)) = A277316(n).
%F A260443 a(A186891(1+n)) = A277318(n). [Subsequence for irreducible polynomials].
%e A260443 n    a(n)   prime factorization    Stern polynomial
%e A260443 ------------------------------------------------------------
%e A260443 0       1   (empty)                B_0(x) = 0
%e A260443 1       2   p_1                    B_1(x) = 1
%e A260443 2       3   p_2                    B_2(x) = x
%e A260443 3       6   p_2 * p_1              B_3(x) = x + 1
%e A260443 4       5   p_3                    B_4(x) = x^2
%e A260443 5      18   p_2^2 * p_1            B_5(x) = 2x + 1
%e A260443 6      15   p_3 * p_2              B_6(x) = x^2 + x
%e A260443 7      30   p_3 * p_2 * p_1        B_7(x) = x^2 + x + 1
%e A260443 8       7   p_4                    B_8(x) = x^3
%e A260443 9      90   p_3 * p_2^2 * p_1      B_9(x) = x^2 + 2x + 1
%p A260443 b:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
%p A260443 a:= proc(n) option remember; `if`(n<2, n+1,
%p A260443       `if`(irem(n, 2, 'h')=0, b(a(h)), a(h)*a(n-h)))
%p A260443     end:
%p A260443 seq(a(n), n=0..56);  # _Alois P. Heinz_, Jul 04 2024
%t A260443 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 *)
%o A260443 (PARI)
%o A260443 A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From _Michel Marcus_
%o A260443 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.
%o A260443 \\ _Antti Karttunen_, Oct 11 2016
%o A260443 (Scheme)
%o A260443 ;; Uses memoization-macro definec:
%o A260443 (definec (A260443 n) (cond ((<= n 1) (+ 1 n)) ((even? n) (A003961 (A260443 (/ n 2)))) (else (* (A260443 (/ (- n 1) 2)) (A260443 (/ (+ n 1) 2))))))
%o A260443 ;; A more standalone version added Oct 10 2016, requiring only an implementation of A000040 and the memoization-macro definec:
%o A260443 (define (A260443 n) (product_primes_to_kth_powers (A260443as_coeff_list n)))
%o A260443 (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))))))
%o A260443 (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))))))
%o A260443 (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)))))))
%o A260443 (Python)
%o A260443 from sympy import factorint, prime, primepi
%o A260443 from functools import reduce
%o A260443 from operator import mul
%o A260443 def a003961(n):
%o A260443     F = factorint(n)
%o A260443     return 1 if n==1 else reduce(mul, (prime(primepi(i) + 1)**F[i] for i in F))
%o A260443 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)
%o A260443 print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 21 2017
%Y A260443 Same sequence sorted into ascending order: A260442.
%Y A260443 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.
%Y A260443 Cf. also A048675, A277333 (left inverses).
%Y A260443 Cf. A277323, A277324 (bisections), A277200 (even terms sorted), A277197 (first differences), A277198.
%Y A260443 Cf. A277316 (values at primes), A277318.
%Y A260443 Cf. A023758 (positions of squarefree terms), A101082 (of terms not squarefree), A277702 (positions of records), A277703 (their values).
%Y A260443 Cf. A283992, A283993 (number of irreducible, reducible polynomials in range 1 .. n).
%Y A260443 Cf. also A206296 (Fibonacci polynomials similarly represented).
%K A260443 nonn,look
%O A260443 0,2
%A A260443 _Antti Karttunen_, Jul 28 2015
%E A260443 More linking formulas added by _Antti Karttunen_, Mar 21 2017