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