Mike Speciner - cp's OEIS frontend

A384342 Largest minimum height of the irreducible factors of a degree-n polynomial of height 1.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2

Offset: 1

Mike Speciner, May 26 2025

			For n < 12, every height 1 degree n polynomial has a height 1 irreducible factor, so a(n) = 1.
For n = 12, x^12-x^11-x^9-x^8+x^6-x^4+x^3+x+1 = (x^6-2x^5+x^4-x^2+x-1)(x^6+x^5+x^4-x^2-2x-1) is the product of two irreducible polynomials of height 2, so a(12) >= 2; and every degree 12 height 1 polynomial has an irreducible factor of height at most 2, so a(12) = 2.

Cf. A363959 gives max height of max-height irreducible factor, whereas this sequence gives max height of min-height irreducible factor.

from msmath.poly import polynomial as poly
def height(p) :
  """find the height, i.e. max abs coeff, of poly p"""
  return max(map(abs, p));
def height1(n) :
  """generate all height 1 polys of degree n"""
  for a in range(3**n) :
    p = [1];
    for i in range(n) :
      a, r = divmod(a, 3);
      p.append(r-1);
    yield poly(*p);
def a(n) :
  """Return max min height of the irreducible factors of a degree n height 1 poly"""
  highest = 0;
  for p in height1(n) :
    f = p.factor();
    h = min(map(height, f));
    if highest < h:
      highest = h;
  return highest;

A379677 Numbers k for which 10k+1, 10k+3, 10k+7, 10k+9, 10k+31, 10k+33, 10k+37, and 10k+39 are primes.

Original entry on oeis.org

100630, 259495, 391921, 960055, 1053106, 10881631, 13144570, 15237073, 15713164, 17902876, 21195025, 25535221, 26758786, 55745863, 68512435, 72449137, 82135765, 87141136, 103026208, 110310436, 128216002, 138120127, 142769863, 143237995, 144399400, 159672133, 194876008

Offset: 1

Mike Speciner, Dec 29 2024

nonn

k is a term if k and k+3 are both in A007811.

			a(1) = 100630 since 1006301, 1006303, 1006307, 1006309, 1006331, 1006333, 1006337, and 1006339 are all prime and there are no smaller minimally close prime decades.

Cf. A007811, A059925.

from itertools import count
from sympy import isprime
def generate_a() :
  for k in count() :
    for j in (1,3,7,9,31,33,37,39) :
      if not isprime(10*k+j) : break
    else:
      yield k

From Hugo Pfoertner, Dec 29 2024: (Start)
a(n) = (A059925(n) - 1)/10.
a(n) == 19 (mod 21). (End)

More terms from Hugo Pfoertner, Dec 29 2024

A372953 Orders of finite fields where -1 is a square.

Original entry on oeis.org

2, 4, 5, 8, 9, 13, 16, 17, 25, 29, 32, 37, 41, 49, 53, 61, 64, 73, 81, 89, 97, 101, 109, 113, 121, 125, 128, 137, 149, 157, 169, 173, 181, 193, 197, 229, 233, 241, 256, 257, 269, 277, 281, 289, 293, 313, 317, 337, 349, 353, 361, 373, 389, 397, 401, 409, 421, 433, 449, 457, 461

Offset: 1

Mike Speciner, May 17 2024

The sequence comprises the positive powers of 2, the positive powers of primes congruent to 1 mod 4, and the positive even powers of primes congruent to 3 mod 4.

The multiplication group of GF(p^n) is cyclic of order o = p^n-1. For p=2, 1=-1, so 1 is a square root of -1. Otherwise, -1 has order 2 and so any square root of -1 has order 4. So, for there to be a square root of -1, o mod 4 must be 0, i.e. p^n mod 4 = 1. Then if g is a generator of the group, g^(o/4) is a square root of -1. p^n mod 4 = 1 if and only if p mod 4 = 1 or p mod 4 = 3 and n is even.

Cf. A000040 (primes), A000961 (prime powers).

Symmetric difference of A000079 (power of 2) and A085759 (prime powers congruent to 1 mod 4).

from itertools import count
from msmath.numfuns import primepower
def a(start=2,stop=None) :
  for n in range(start,stop) if stop else count(start):
    if primepower(n) :
      if n%4 != 3: yield n

A368594 Number of Lucas numbers needed to get n by addition and subtraction.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 3, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3

Offset: 0

Mike Speciner, Dec 31 2023

nonn

The definition does not require the Lucas numbers to be distinct, but it is easy to show that a(n) distinct Lucas numbers can get n by addition and subtraction, based on the identity 2*Lucas(n) = Lucas(n+1)+Lucas(n-2).

			a(0) = 0, as it is the empty sum of Lucas numbers.
a(1) = a(2) = a(3) = a(4) = 1, as they are all Lucas numbers.
a(5) = 2, since 5 = 1 + 4 = 2 + 3.
The first term requiring a subtraction is a(16): 16 = 18 - 2.

Mike Speciner, graphic representation of this and 5 similar sequences
Mike Speciner, graphic representation of this and 5 similar sequences

Cf. A000032 (Lucas numbers).
Cf. A364754 (indices of record highs).
Cf. A367816, A116543 (where only addition is allowed).
Cf. A058978 (for Fibonacci numbers).

from itertools import count
def a(n) :
  """For integer n, the least number of signed Lucas terms required to sum to n."""
  f = [2, 1];    # Lucas numbers, starting with Lucas(0)
  while f[-1] <= (n or 1) :
    f.append(f[-2]+f[-1])
  a = [0 for _ in range(f[-1]+1)]
  for i in f :
    a[i] = 1
  for c in count(2) :
    if not all(a[4:]) :
      for i in range(4, f[-1]) :
        if not a[i] :
          for j in f :
            if j >= i :
              break
            if a[i-j] == c-1 :
              a[i] = c
              break
          if not a[i]:
            for j in f :
              if i+j >= len(a) :
                if j != 2:
                  break
              elif a[i+j] == c-1 :
                a[i] = c
                break;
    else :
      break
  return a[n]

a(0) = 0; a(A000032(n)) = 1.

a(n) = 1 + min_{k>=0} min(a(n-Lucas(k)), a(n+Lucas(k))), for n >= 1.

A367817 Number of terms in a shortest sequence of Fibonacci numbers that sum to n, allowing Fibonacci numbers with negative indices.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3, 2, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 2, 3, 2, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 2, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 4, 3, 4, 3, 2, 3, 3, 3

Offset: 0

Mike Speciner, Dec 01 2023

a(A001076(n)) is the first occurrence of n.

			For n = 0, the empty sequence sums to 0, so a(0) = 0.
For n = 1, 2, 3, 5, 8, 13 each n is a Fibonacci number, so a(n) = 1.
The first n needing a negative-index Fibonacci number is 12 = 13 + -1; a(12) = 2.

Cf. A000045 (Fibonacci numbers), A039834 (negative index Fibonacci numbers).
Cf. A007895 (similar but with negative index Fibonacci numbers not allowed).
Cf. A001076.

from itertools import count
def  a(n) :
  """For integer n, the least number of Fibonacci terms required to sum to n."""
  f = [1,2];    # Fibonacci numbers, starting with Fibonacci(2)
  while f[-1] <= n :
    f.append(f[-2]+f[-1]);
  a = [0 for _ in range(f[-1]+1)];
  for i in f :
    a[i] = 1;
  for c in count(2) :
    if not all(a[4:]) :
      for i in range(4,f[-1]) :
        if not a[i] :
          for j in f :
            if j >= i :
              break;
            if a[i-j] == c-1 :
              a[i] = c;
              break;
          if not a[i]:
            for j in f[::2] :
              if i+j >= len(a) :
                break;
              if a[i+j] == c-1 :
                a[i] = c;
                break;
    else :
      break;
  return a[n];

a(0) = 0; a(A000045(n)) = 1 for n > 0.

For n > 0, a(n) = 1 + min(a(n-Fibonacci(k))) where k ranges over Z.

A367816 Number of terms in a shortest sequence of Lucas numbers that sum to n, allowing Lucas numbers with negative indices.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 2, 1, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 1, 2, 2, 2

Offset: 0

Mike Speciner, Dec 01 2023

			For n = 0, the empty sequence sums to 0, so a(0) = 0.
For n = 1, 2, 3, 4, 7, 11, 18, each n is a Lucas number, so a(n) = 1.
The first n needing a negative-index Lucas number is 17 = 18 + -1; a(17) = 2.

Cf. A000032 Lucas numbers; A061084 negative index Lucas numbers.
A116543 is the similar sequence where negative index Lucas numbers are not allowed.
a(A365907(n)) is the first occurrence of n.

from itertools import count
def  a(n) :
  """For integer n, the least number of Lucas terms required to sum to n."""
  f = [2,1];    # Lucas numbers, starting with Lucas(0)
  while f[-1] <= (n or 1) :
    f.append(f[-2]+f[-1]);
  a = [0 for _ in range(f[-1]+1)];
  for i in f :
    a[i] = 1;
  for c in count(2) :
    if not all(a[4:]) :
      for i in range(4,f[-1]) :
        if not a[i] :
          for j in f :
            if j >= i :
              break;
            if a[i-j] == c-1 :
              a[i] = c;
              break;
          if not a[i]:
            for j in f[1::2] :
              if i+j >= len(a) :
                break;
              if a[i+j] == c-1 :
                a[i] = c;
                break;
    else :
      break;
  return a[n];

a(0) = 0; a(A000032(n)) = 1.

For n > 0, a(n) = 1+min(a(n-Lucas(k))) where k ranges over Z.

A364754 Smallest nonnegative integer not expressible by the addition and subtraction of fewer than n Lucas numbers.

Original entry on oeis.org

0, 1, 5, 23, 99, 421, 1785, 7563, 32039, 135721, 574925, 2435423, 10316619, 43701901, 185124225, 784198803, 3321919439, 14071876561, 59609425685, 252509579303, 1069647742899, 4531100550901, 19194049946505, 81307300336923, 344423251294199, 1459000305513721, 6180424473349085

Offset: 0

Mike Speciner, Oct 20 2023

			a(0) = 0, since 0 is expressible as the sum of 0 Lucas numbers.
a(1) = 1, since 1 is a Lucas number.
a(2) = 5, since 2, 3, and 4 are all Lucas numbers; while 5=1+4, the sum of 2 Lucas numbers.
a(3) = 23, since integers less than 23 are expressible with 2 or fewer Lucas numbers, while 23 = 1+4+18 requires 3 terms.

Index entries for linear recurrences with constant coefficients, signature (5,-3,-1).

Cf. A000032, A004146 (adding positive Lucas numbers), A365907 (adding any Lucas numbers).

Cf. A001076 (with Fibonacci numbers).

a[n_] := (LucasL[3*n - 1] - 1)/2; a[0] = 0; Array[a, 27, 0] (* Amiram Eldar, Oct 21 2023 *)

from sympy import lucas
a = lambda n: n and (lucas(3*n-1)-1)//2

a(0) = 0.
a(n) = (A000032(3*n-1)-1)/2, for n > 0.
a(n) = 1 + Sum_{i=1..n-1} A000032(3*i), for n > 0.
G.f.: x*(1 + x^2)/((1 - x)*(1 - 4*x - x^2)). -  Stefano Spezia, Oct 21 2023

A365907 Smallest nonnegative integer that is not the sum of fewer than n signed Lucas numbers.

Original entry on oeis.org

0, 1, 5, 16, 63, 262, 1105, 4676, 19803, 83882, 355325, 1505176, 6376023, 27009262, 114413065, 484661516, 2053059123, 8696898002, 36840651125, 156059502496, 661078661103, 2800374146902, 11862575248705, 50250675141716, 212865275815563, 901711778403962

Offset: 0

Mike Speciner, Sep 22 2023

Signed Lucas numbers are the union of A000032 and A061084.

			a(0) = 0, the sum of 0 Lucas numbers.
a(1) = 1 = A000032(1), the sum of 1 Lucas number.
a(2) = 5 = 1+4 = A000032(1)+A000032(3), the sum of 2 Lucas numbers. (2, 3, and 4 need only one term, since they are Lucas numbers.)
a(4) = 63 = 1+4+11+47.
For comparison, 45 is the first sum requiring 4 positive Lucas numbers (45 = 1+4+11+29, see A004146), but here 45 = 47+2-4 requires only 3 signed Lucas numbers so that a(4) != 45.

Index entries for linear recurrences with constant coefficients, signature (5,-3,-1).

Cf. A000032, A061084, A004146 (analogous with only positive Lucas numbers).

LinearRecurrence[{5, -3, -1}, {0, 1, 5, 16, 63}, 26] (* Amiram Eldar, Sep 26 2023 *)

from sympy import lucas
a = lambda n: n if n<2 else (lucas(3*n-2)+3)//2

a(n) = n, for n<2.
a(n) = (A000032(3*n-2)+3)/2 = 1+4+Sum_{i=2..n-1} A000032(3*n-1), for n>1.
G.f.: x*(1 - 6*x^2 - x^3)/((1 - x)*(1 - 4*x - x^2)). - Stefano Spezia, Sep 25 2023

A363959 Maximum height of an irreducible factor of any degree-n polynomial of height 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 9, 9, 11, 14, 16, 17, 25, 33, 39

Offset: 1

Mike Speciner, Jun 29 2023

We consider only polynomials with integer coefficients (Z[x]).
The sequence is increasing, since we can always multiply the best degree n-1 polynomial by x. I suspect (but haven't proven) that if we only considered polynomials with nonzero constant term, we'd get the same sequence.
Note that if we consider all factors, not just irreducible ones, then the resulting sequence would be bounded below by A114536.

			We will assume that the coefficient of x^n is 1. (If not, just multiply by -1.) Similarly, we can insist that all the factors will also have high order coefficient 1.
For n = 1, all degree 1 polynomials are irreducible, so they are their own irreducible factors, and so all their irreducible factors have the same height as them. Thus a(1) = 1.
For n = 2, the height 1 degree 2 polynomials and their factorizations are
  x^2-x-1 irreducible,
  x^2-x = (x-1)x,
  x^2-x+1 irreducible,
  x^2-1 = (x-1)(x+1),
  x^2 = x^2,
  x^2+1 irreducible,
  x^2+x-1 irreducible,
  x^2+x = x(x+1),
  x^2+x+1 irreducible.
All the irreducible factors have height 1, so a(2) = 1.
For n = 12, we have x^12-x^11+x^10+x^9-x^8+x^7-x^6+x^5+x^4+x^3-x+1 = (x+1)^2*(x^10-3x^9+6x^8-8x^7+9x^6-9x^5+8x^4-6x^3+5x^2-3x+1).
The height (maximum absolute value of the coefficients) of the product is 1, while the height of the final irreducible factor is 9.
No other height 1 degree 12 polynomial has an irreducible factor with larger height.
So a(12) = 9.

Mike Speciner, Corresponding height 1 polynomials

from msmath.poly import polynomial as poly
def height(p) :
  """find the height, i.e. max abs coeff, of poly p"""
  return max(map(abs,p));
def height1(n) :
  """generate all height 1 polys of degree n"""
  for a in range(3**n) :
    p = [1];
    for i in range(n) :
      a,r = divmod(a,3);
      p.append(r-1);
    yield poly(*p);
def a(n) :
  """Return highest height of any irreducible factor of any degree n height 1 poly"""
  highest = (0,0);
  for p in height1(n) :
    f = p.factor();
    h = max(map(lambda f:(height(f),-f.degree),f));
    if highest < h:
      highest = h;
      best = sorted(f,key=len);
      best = {x:f[x] for x in best};
  return highest[0];

a(20) from Mike Speciner, Jul 09 2025

A323845 Number of inequivalent height 1 degree n polynomials with nonzero constant term.

Original entry on oeis.org

1, 4, 6, 21, 45, 144, 378, 1161, 3321, 10044, 29646, 89181, 266085, 798984, 2392578, 7179921, 21526641, 64586484, 193720086, 581179941, 1743421725, 5230324224, 15690618378, 47072032281, 141215033961, 423645633324, 1270933711326, 3812802728301, 11438398618965, 34315200639864

Offset: 1

Mike Speciner, Aug 26 2023

A height 1 degree n polynomial p(x) is considered equivalent to -p(x), p(-x), x^n * p(1/x). Together, these transformations (polynomial negation, variable negation, variable inversion) generate an equivalence relationship among height 1 degree n polynomials with nonzero constant term. Two equivalent polynomials have equivalent factorizations.
If we consider only monic polynomials, equivalence classes can comprise 1, 2, or 4 different polynomials.
Proof for n = 2k+1: There are 2*3^2k monic degree n height 1 polynomials with nonzero constant term. Of those, 2*3^k are transformed to themselves by p(0)*x^n*p(1/x). For odd degree monic polynomials, that is the only equivalence transformation that has a fixed point. The number of equivalence classes is thus 2*3^k/2 + (2*3^2k-2*3^k)/4 = 3^k*(3^k+1)/2.
Proof for n = 2k+2:
Let T be the set of monic height 1 degree-n polynomials with nonzero constant term.
Let V be the subset for which p(0)*x^n*p(1/x) = p(x).
Let N be the subset for which p(-x) = p(x).
Let G be the subset for which p(0)*x^n*p(-1/x) = p(x).
Let A be the intersection of V, N, and G.
A comprises the elements of T in 1-element equivalence classes.
V-A, N-A, and G-A are disjoint. Their union comprises the elements of T in 2-element equivalence classes.
The remaining element of T are those in 4-element equivalence classes.
The number of equivalence classes is |A| + (|V-A|+|N-A|+|G-A|)/2 + |T-A-(V-A)-(N-A)-(G-A)|/4 = |A|+(|V|+|N|+|G|-3|A|)/2 + (|T|-|V|-|N|-|G|+2|A|)/4 = (|T|+|V|+|N|+|G|)/4.
It is not hard to show |T|=2*3^(2k+1), |V|=|G| = 4*3^k and |N| = 2*3^k. Then we have (|T|-|V|-|N|-|G|)/4 = 3^k*(3^(k+1)+2+1+2)/2 = 3^k*(3^(k+1)+5)/2.

			For n = 2, the degree 2 height 1 polynomials with nonzero constant term are x^2-x-1, x^2-x+1, x^2-1, x^2+1, x^2+x-1, x^2+x+1, and their (equivalent) negatives. x^2-x-1 is equivalent to x^2+x-1 (either by variable negation or a combination of variable inversion and polynomial negation), and x^2-x+1 is equivalent to x^2+x+1 (by variable negation), while x^2+1 and x^2-1 are each (together with their negative) in their own equivalence class, so a(2) = 4.

Mike Speciner, Python code to compute a(n) by counting equivalence classes
Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

LinearRecurrence[{3, 3, -9}, {1, 4, 6}, 30] (* Amiram Eldar, Sep 02 2023 *)

def a(n) :
  k = (n-1)//2;
  return 3**k*((3**k+1) if n&1 else (3**(k+1)+5))//2 if n else 1;

a(2k+1) = 3^k*(3^k+1)/2, and a(2k+2) = 3^k*(3^(k+1)+5)/2.

G.f.: x*(1 + x - 9*x^2)/((1 - 3*x)*(1 - 3*x^2)). - Stefano Spezia, Sep 02 2023

cp's OEIS Frontend

User: Mike Speciner

A384342 Largest minimum height of the irreducible factors of a degree-n polynomial of height 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

A379677 Numbers k for which 10k+1, 10k+3, 10k+7, 10k+9, 10k+31, 10k+33, 10k+37, and 10k+39 are primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

Extensions

A372953 Orders of finite fields where -1 is a square.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

A368594 Number of Lucas numbers needed to get n by addition and subtraction.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A367817 Number of terms in a shortest sequence of Fibonacci numbers that sum to n, allowing Fibonacci numbers with negative indices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A367816 Number of terms in a shortest sequence of Lucas numbers that sum to n, allowing Lucas numbers with negative indices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Formula

A364754 Smallest nonnegative integer not expressible by the addition and subtraction of fewer than n Lucas numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A365907 Smallest nonnegative integer that is not the sum of fewer than n signed Lucas numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica