A277318 -id:A277318 - 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).

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

Antti Karttunen, Jul 28 2015

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

			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

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

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

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

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

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

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

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

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

More linking formulas added by Antti Karttunen, Mar 21 2017

A186891 Numbers n such that the Stern polynomial B(n,x) is irreducible.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 157, 161, 163, 167, 169, 173, 175, 179, 181, 185, 191, 193, 197, 199

Offset: 1

T. D. Noe, Feb 28 2011

nonn

Ulas and Ulas conjecture that all primes are here. The nonprime n are in A186892. See A186886 for the least number having n prime factors.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Maciej Ulas and Oliwia Ulas, On certain arithmetic properties of Stern polynomials, arXiv:1102.5109 [math.CO], 2011.

Cf. A057526 (degree of Stern polynomials), A125184, A260443 (Stern polynomials).
Cf. A186892 (subsequence of nonprime terms).
Cf. A186893 (subsequence for self-reciprocal polynomials).
Positions of 0 and 1's in A277013, Positions of 1 and 2's in A284011.
Cf. A283991 (characteristic function for terms > 1).
Cf. also A186886, A277190, A277318, A283992.

ps[n_] := ps[n] = If[n<2, n, If[OddQ[n], ps[Quotient[n, 2]] + ps[Quotient[n, 2] + 1], x ps[Quotient[n, 2]]]];
selQ[n_] := IrreduciblePolynomialQ[ps[n]];
Join[{1}, Select[Range[200], selQ]] (* Jean-François Alcover, Nov 02 2018, translated from PARI *)

ps(n)=if(n<2, n, if(n%2, ps(n\2)+ps(n\2+1), 'x*ps(n\2)))
is(n)=polisirreducible(ps(n)) \\ Charles R Greathouse IV, Apr 07 2015

From Antti Karttunen, Mar 21 2017: (Start)
A283992(a(1+n)) = n.
A260443(a(1+n)) = A277318(n).
(End)

A206284 Numbers that match irreducible polynomials over the nonnegative integers.

Original entry on oeis.org

3, 6, 9, 10, 12, 18, 20, 22, 24, 27, 28, 30, 36, 40, 42, 44, 46, 48, 50, 52, 54, 56, 60, 66, 68, 70, 72, 76, 80, 81, 88, 92, 96, 98, 100, 102, 104, 108, 112, 114, 116, 118, 120, 124, 126, 130, 132, 136, 140, 144, 148, 150, 152, 154, 160, 162, 164, 168, 170

Offset: 1

Clark Kimberling, Feb 05 2012

nonn

Starting with 1, which encodes 0-polynomial, each integer m encodes (or "matches") a polynomial p(m,x) with nonnegative integer coefficients determined by the prime factorization of m. Write m = prime(1)^e(1) * prime(2)^e(2) * ... * prime(k)^e(k); then p(m,x) = e(1) + e(2)x + e(3)x^2 + ... + e(k)x^k.
Identities:
  p(m*n,x) = p(m,x) + p(n,x),
  p(m*n,x) = p(gcd(m,n),x) + p(lcm(m,n),x),
  p(m+n,x) = p(gcd(m,n),x) + p((m+n)/gcd(m,n),x), so that if A003057 is read as a square matrix, then
  p(A003057,x) = p(A003989,x) + p(A106448,x).
Apart from powers of 3, all terms are even. - Charles R Greathouse IV, Feb 11 2012
Contains 2*p^m and p*2^m if p is an odd prime and m is in A052485. - Robert Israel, Oct 09 2016

			Polynomials having nonnegative integer coefficients are matched to the positive integers as follows:
   m    p(m,x)    irreducible
  ---------------------------
   1    0         no
   2    1         no
   3    x         yes
   4    2         no
   5    x^2       no
   6    1+x       yes
   7    x^3       no
   8    3         no
   9    2x        yes
  10    1+x^2     yes

Antti Karttunen, Table of n, a(n) for n = 1..10566

Cf. A052485, A206285 (complement), A206296.
Positions of ones in A277322.
Terms of A277318 form a proper subset of this sequence. Cf. also A277316.
Other sequences about factorization in the same polynomial ring: A206442, A284010.
Polynomial multiplication using the same encoding: A297845.

P:= n -> add(f[2]*x^(numtheory:-pi(f[1])-1), f =  ifactors(n)[2]):
select(irreduc @ P, [$1..200]); # Robert Israel, Oct 09 2016

b[n_] := Table[x^k, {k, 0, n}];
f[n_] := f[n] = FactorInteger[n]; z = 400;
t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]]
== Prime[k], f[n][[m, 2]], 0];
u = Table[Apply[Plus,
    Table[Table[t[n, m, k], {k, 1, PrimePi[n]}], {m, 1,
      Length[f[n]]}]], {n, 1, z}];
p[n_, x_] := u[[n]].b[-1 + Length[u[[n]]]]
Table[p[n, x], {n, 1, z/4}]
v = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
AppendTo[v, n]], {n, z/2}]; v  (* A206284 *)
Complement[Range[200], v]      (* A206285 *)

is(n)=my(f=factor(n));polisirreducible(sum(i=1, #f[,1], f[i,2]*'x^primepi(f[i,1]-1))) \\ Charles R Greathouse IV, Feb 12 2012

Introductory comments edited by Antti Karttunen, Oct 09 2016 and Peter Munn, Aug 13 2022

A260442 Sequence A260443 sorted into ascending order.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 11, 13, 15, 17, 18, 19, 23, 29, 30, 31, 35, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 75, 77, 79, 83, 89, 90, 97, 101, 103, 105, 107, 109, 113, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 210, 211, 221, 223, 227, 229, 233, 239, 241, 245, 251, 257, 263, 269, 270, 271, 277, 281, 283, 293, 307, 311

Offset: 0

Antti Karttunen, Jul 29 2015

nonn

Each term is a prime factorization encoding of one of the Stern polynomials. See A260443 for details.

Numbers n for which A260443(A048675(n)) = n. - Antti Karttunen, Oct 14 2016

Antti Karttunen, Table of n, a(n) for n = 0..10000

Cf. A003961, A048675, A260443.
Subsequence of A073491.
From 2 onward the positions of nonzeros in A277333.
Various subsequences: A000040, A002110, A070826, A277317, A277200 (even terms).  Also all terms of A277318 are included here.
Cf. also A277323, A277324 and permutation pair A277415 & A277416.

allocatemem(2^30);
A048675(n) = my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; \\ Michel Marcus, Oct 10 2016
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))));
isA260442(n) = (A260443(A048675(n)) == n);  \\ The most naive version.
A055396(n) = if(n==1, 0, primepi(factor(n)[1, 1])) \\ Charles R Greathouse IV, Apr 23 2015
A061395(n) =  if(1==n, 0, primepi(vecmax(factor(n)[, 1]))); \\ After M. F. Hasler's code for A006530.
isA260442(n) = ((1==n) || isprime(n) || ((omega(n) == 1+(A061395(n)-A055396(n))) && (A260443(A048675(n)) == n))); \\ Somewhat optimized.
i=0; n=0; while(i < 10001, n++; if(isA260442(n), write("b260442.txt", i, " ", n); i++));
\\ Antti Karttunen, Oct 14 2016

from sympy import factorint, prime, primepi
from operator import mul
from functools import reduce
def a048675(n):
    F=factorint(n)
    return 0 if n==1 else sum([F[i]*2**(primepi(i) - 1) for i in F])
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([n for n in range(301) if a(a048675(n))==n]) # Indranil Ghosh, Jun 21 2017

;; With Antti Karttunen's IntSeq-library.
(define A260442 (FIXED-POINTS 0 1 (COMPOSE A260443 A048675)))
;; An optimized version:
(define A260442 (MATCHING-POS 0 1 (lambda (n) (or (= 1 n) (= 1 (A010051 n)) (and (not (< (A001221 n) (+ 1 (A243055 n)))) (= n (A260443 (A048675 n))))))))
;; Antti Karttunen, Oct 14 2016

A277316 Prime-factorization representation of the prime-th Stern-polynomial: a(n) = A260443(A000040(n)).

Original entry on oeis.org

3, 6, 18, 30, 270, 450, 630, 6750, 9450, 22050, 2310, 3543750, 4961250, 53156250, 727650, 173643750, 25467750, 2668050, 40020750, 891371250, 9550406250, 1400726250, 3190703906250, 467969906250, 173423250, 16378946718750, 1715889656250, 245684200781250, 25738344843750, 8497739250, 510510, 6763506750, 66919696593750

Offset: 1

Antti Karttunen, Oct 10 2016

nonn

If the conjecture by Ulas and Ulas is true, then all these terms can be found from A206284 and then this is also a subsequence of A277318.

Antti Karttunen, Table of n, a(n) for n = 1..1028
Maciej Ulas and Oliwia Ulas, On certain arithmetic properties of Stern polynomials, arXiv:1102.5109 [math.CO], 2011.

Cf. A000040, A206284, A260443.
Cf. A277317 (same sequence sorted into ascending order) is a subsequence of A277319.
Differs from A277318 for the first time at n=10, where A277318(10) = 15750, a term which is missing from this sequence.

(define (A277316 n) (A260443 (A000040 n)))

a(n) = A260443(A000040(n)).
Other identities.
For all n >= 1, a(A059305(n)) = A002110(A000043(n)).

A277200 Even terms in A260442 (in A260443).

Original entry on oeis.org

2, 6, 18, 30, 90, 210, 270, 450, 630, 2310, 6750, 6930, 9450, 15750, 20250, 22050, 30030, 47250, 90090, 330750, 510510, 727650, 1212750, 1531530, 1653750, 2668050, 3543750, 4961250, 8489250, 9699690, 18191250, 24806250, 25467750, 29099070, 40020750, 53156250, 57881250, 104053950, 173423250, 173643750

Offset: 1

Antti Karttunen, Oct 14 2016

nonn

All odd terms larger > 1 in A260442 can be obtained from these terms by shifting their prime factorization some number of steps towards larger primes with A003961.

Cf. A003961, A260442, A260443.
Sequence A277324 sorted into ascending order.
Subsequence of A055932.
Cf. A002110, A277317 (subsequences, apart from their initial terms).
Also all terms of A277318 apart from initial 3 are included in this sequence.

allocatemem(2^30);
A061395(n) =  if(1==n, 0, primepi(vecmax(factor(n)[, 1]))); \\ After M. F. Hasler's code for A006530.
A048675(n) = my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; \\ Michel Marcus, Oct 10 2016
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))));
isA277200(n) = (!(n%2) && (omega(n) == A061395(n)) && (A260443(A048675(n)) == n));
i=1; n=0; while(i < 100, n++; if(isA277200(n), write("b277200.txt", i, " ", n); i++));

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Scheme

Formula

Extensions

A186891 Numbers n such that the Stern polynomial B(n,x) is irreducible.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A206284 Numbers that match irreducible polynomials over the nonnegative integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A260442 Sequence A260443 sorted into ascending order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Scheme

A277316 Prime-factorization representation of the prime-th Stern-polynomial: a(n) = A260443(A000040(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A277200 Even terms in A260442 (in A260443).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI