Print all Polynomials

Question

The set of all polynomials with integer coefficients is countable. This means that there is a sequence that contains each polynomial with integer coefficients exactly once.

Your goal is it to write a function or program that outputs such a sequence.

Example (you may use another sequence):

// list of integers [i -> Z(i)] : 0,1,-1,2,-2,...
// integer -> polynomial
// 1. factor index n=product_i p_i^k_i
// 2. return polynomial sum_i Z(k_i)*x^(i-1)
1 -> 0     // all powers 0 -> all summands 0
2 -> 1     // 2^1 -> 1*x^0
3 -> x     // 3^1 -> 1*x^1
4 -> -1    // 2^2 -> -1*x^0
5 -> x²    // 5^1 -> 1*x^2
6 -> x+1   // 2^1*3^1 -> 1*x^0+1*x^1
7 -> x³    // 7^1 -> 1*x^3
8 -> 2     // 2^3 -> 2*x^0
9 -> -x    // 3^2 -> -1*x^1
...

For ideas how to compute the sequence of all integers see here

Rules:

• Each integer polynomial has to (eventually) appear in the sequence generated by your program
• Polynomials are not allowed to appear more than once
• The standard sequence IO-rules apply
• You may output polynomials as lists of coefficients
• Using the empty string/list to represent zero is allowed
• You are allowed to output the coefficients in reverse order (constant coefficient on the left)
• This is code-golf the shortest program (per language) wins.

Answer 1

Python, 56 bytes

P=[[0]]
for*t,h in P:print(P[-1]);P+=t+[h,0],t+[(h<1)-h]

Try it online!

Prints lists indefinitely as polynomials reversed. The idea is that every nonempty list of integers is generated uniquely by repeatedly applying one of two operations starting from the singleton [0]:

1. Append a [0]
2. Advance the last element h via the map h -> (h<=0)-h, which walks through the integers as 0, 1, -1, 2, -2, 3, -3, ....

We do a breadth-first walk on this infinite binary tree to generate all these lists. To do this, we keep a list P of nodes to explore starting with just the root [0], iterate over it, and when we explore a node l, we append to P the two children of l.

Note that branch (1) creates the lists with a trailing 0 and branch (2) creates all those starting with any other value. So, outputting just the branch (2) nodes gives all nonzero polynomials represented without extra trailing zeroes. We do this by repeatedly printing the last element of P after doing the append which puts the branch (2) result last. By also doing this print at the start, we also output the zero polynomial at the root of P, which we'd otherwise miss.

Thanks to loopy walt for -1 byte by flipping the order and Jonathan Allan for -1 from not using <=.

Answer 2

Python, 75 bytes

f=lambda s:s*[0]and[s%-2^r(s//4)]+f(r(s//2))
r=lambda s:s and s%2^2*r(s//4)

Attempt This Online!

^^^ Version without string intermediates.

Python, 48 bytes

f=lambda n,i:n and(n>>2**i-1&1)-2*f(n>>2*2**i,i)

Attempt This Online!

^^^ This one may be illegal: It takes enumeration index and coefficient index and returns only that coefficient.

Uses @Bubbler's negabinaries instead of my previous method.

Python, 107 bytes

lambda n:g(f"{n:b}"[::-1])or[0]
g=lambda s:"1"in s and[-(s[0]>"0")^int("0"+s[2::2][::-1],2)]+g(s[1::2])or[]

Attempt This Online!

If representing the 0 polynomial by the empty list is acceptable, we can save 5 as @JonathanAllan points out.

Python, 102 bytes

lambda n:g(f"{n:b}"[::-1])
g=lambda s:"1"in s and[-(s[0]>"0")^int("0"+s[2::2][::-1],2)]+g(s[1::2])or[]

Attempt This Online!

Does not use prime factors. Expects a nonnegative integer and returns the coefficients lowest (constant) to highest.

How?

Uses binary representation. Coefficient 0 encoded in bits (least significant to most) 1,3,5,7,9,... coefficient 1 encoded in bits 2,6,10,14,..., coefficient 2 encoded in bits 4,12,20,28,..., etc. The bits are simply read as a binary number except that the lsb encodes the sign (more precisely, the presence or absence of a tilde operator i.e. 0 <-> -1, 1 <-> -2, etc. Advantage over "naive" -: no redundancy at 0.)

Answer 3

Nekomata, 10 bytes

Ňƒ$ƥ←2EƂ∙ŋ

Attempt This Online!

The zero polynomial is represented by 0, and other polynomials are represented by an ascending list of coefficients. For example, x^2 + 2x + 3 is represented by [3, 2, 1].

Ňƒ$ƥ←2EƂ∙ŋ
Ň              Choose a natural number n
 ƒ$ƥ←2EƂ∙      Compute the array of exponents of n's prime factorization.
               This is basically Jelly's ÆE operator
         ŋ     Optionally negate each nonzero element

Answer 4

Jelly,  10  8 bytes

ÆENḂ¡€:2

A monadic Link that accepts a positive integer, \$n\$, and yields the \$n^{\text{th}}\$ integer polynomial as a list of coefficients for increasing powers of \$x\$ with no trailing zeros (i.e. [0, 0, 2, 0, -5] represents \$-5x^4+2x^2\$, and [] represents \$0\$)

Try it online!

How?

ÆENḂ¡€:2 - Link: n
ÆE       - prime factor exponents e.g. n=3*3*7*7*7 -> [0,2,0,3]
     €   - for each {exponent value, e}:
    ¡    -   repeat...
   Ḃ     -   ...number of times: modulo 2 {e} -> 1 if e is odd else 0
  N      -   ...action: negate
      :2 - integer divide by two (vectorises)

This gives the same order as the example sequence, just with negated coefficients.

Answer 5

J, 11 bytes

_2#._#:@q:]

Attempt This Online!

The first half (using prime factorization exponents) is stolen from existing solutions, but the second half is new I guess. To convert "all integers >= 0" to "all integers", I use the negabinary system. That is, convert each nonnegative integer to base 2 and then interpret the binary sequence as base -2. This is shorter in J than doing a "divmod 2".

Jelly, 6 bytes

ÆEBḅ-2

Try it online!

Answer 6

Thunno 2, 9 bytes

ḟıDu@×;2÷

Try it online! or verify a few more cases

Port of Jonathan Allan's Jelly answer.

-1 thanks to @Neil

Explanation

ḟıDu@×;2÷  # Implicit input
ḟ          # Prime factor exponents
 ı    ;    # Map over this list:
  D        #  Duplicate current number
   u@      #  -1 ** that
     ×     #  Multiply by the number
       2÷  # Floor divide each by 2
           # Implicit output

Answer 7

Charcoal, 56 53 51 31 bytes

≔ＩＥ⮌⍘Ｎ²ιθＷθ«≔Φι﹪λ²θ⟦Ｉ↨⮌Φι¬﹪λ²±²

Try it online! Link is to verbose version of code. Outputs the 0-indexed nth polynomial (lowest degree first). Explanation:

≔ＩＥ⮌⍘Ｎ²ιθ

Input n and convert it to base 2. (Note that if an empty output is acceptable for the zero polynomial, then ≔⮌↨Ｎ²θ would suffice, saving 3 bytes.)

Ｗθ«

Repeat until there are no more terms of the polynomial.

≔Φι﹪λ²θ

Remove the current term from the value.

⟦Ｉ↨⮌Φι¬﹪λ²±²

Extract the current term from the previous value and convert it from negabinary for output.

114 111 109 87 bytes to pretty-print the output:

≔⮌↨Ｎ²θＷθ«⊞υ↨⮌Φθ¬﹪λ²±²≔Φθ﹪λ²θ»∨Φ⪫⮌Ｅυ⎇ι⁺⎇∨¬κ⊖↔ι﹪%+dι§ +-ι⎇κ⁺x⎇⊖κ⍘κ”y⁰¹²³⁴⁵⁶⁷⁸⁹”ωωωω∨κ⁻+ι0

Try it online! Link is to verbose version of code. Pretty-prints the 0-indexed nth polynomial. Explanation:

≔⮌↨Ｎ²θ

Input n and convert it to base 2. (Note that if an empty output is acceptable for the zero polynomial, then ≔⮌↨Ｎ²θ would suffice, saving 3 bytes.)

Ｗθ«

Repeat until there are no more terms of the polynomial.

⊞υ↨⮌Φθ¬﹪λ²±²

Extract the current term from the previous value and convert it from negabinary.

≔Φθ﹪λ²θ

Remove the current term from the value.

»∨Φ⪫⮌Ｅυ⎇ι⁺⎇∨¬κ⊖↔ι﹪%+dι§ +-ι⎇κ⁺x⎇⊖κ⍘κ”y⁰¹²³⁴⁵⁶⁷⁸⁹”ωωωω∨κ⁻+ι0

Pretty-print the polynomial. (And I think this must be the first time I've used 4 ωs in a row!)

Edit: Now uses @loopywalt's encoding and @Bubbler's negabinary trick.

Answer 8

Regenerate -a, 35 bytes

|-?[1-9][0-9]*(,(0|-?[1-9][0-9]*))*

Generates polynomials infinitely, given as lists of coefficients from highest to lowest degree. E.g. 1,-2,3 represents \$x^2-2x+3\$. The first result is the empty string, representing \$0\$.

Attempt This Online!

Explanation

Iterating over countable sets is basically Regenerate's whole thing, although since it's designed for generating strings, its number-handling is a bit primitive.

|-?[1-9][0-9]*(,(0|-?[1-9][0-9]*))*
|                                    Either the result is empty, or:
 -?[1-9][0-9]*                       Lead with a nonzero coefficient:
 -?                                   Possibly negative
   [1-9]                              Starts with a nonzero digit
        [0-9]*                        Continues with 0 or more additional digits
              (                  )*  Continue with zero or more further coefficients:
               ,                      Comma to separate from previous coefficient
                (0|             )     Either the coefficient is 0, or it's nonzero:
                   -?                  Possibly negative
                     [1-9]             Starts with a nonzero digit
                          [0-9]*       Continues with 0 or more additional digits

Answer 9

Vyxal r, 36 bits^v2, 4.5 bytes

∆ǏÞnİ

Try it Online!

Ports jelly with a few vyxal specific things.

-15 bits/-1.875 bytes from Bubbler pointing out that Þn exists

Explained

∆ǏÞnİ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌­
∆Ǐ     # ‎⁡To each prime factor exponent from the input
    İ  # ‎⁢get the exponent-th item of
  Þn   # ‎⁣an infinite list of all the integers (positive and negative - 0, 1, -1, 2, -2, ...)
💎

Created with the help of Luminespire.

Answer 10

Scala, 260 bytes

Port of @loopy walt's Python answer in Scala.

---

Golfed version. Attempt This Online!

def D(a:Int,b:Int)=if((a>0&&b>0)||(a<0&&b<0))a/b else if(a%b==0)a/b else a/b-1
def M(a:Int,b:Int)=((a%b)+b)%b
def f(s:Int):List[Int]=s match{case 0=>Nil;case _=>(M(s,-2)^r(D(s,4)))::f(r(D(s,2)))}
def r(s:Int):Int=s match{case 0=>0;case _=>M(s,2)^(2*r(D(s,4)))}

Ungolfed version. Attempt This Online!

object Main {
  def pythonDiv(a: Int, b: Int): Int = {
    if ((a > 0 && b > 0) || (a < 0 && b < 0)) a / b
    else if (a % b == 0) a / b
    else a / b - 1
  }

  def pythonMod(a: Int, b: Int): Int = ((a % b) + b) % b

  def f(s: Int): List[Int] = s match {
    case 0 => Nil
    case _ => List(pythonMod(s, -2) ^ r(pythonDiv(s, 4))) ++ f(r(pythonDiv(s, 2)))
  }

  def r(s: Int): Int = s match {
    case 0 => 0
    case _ => pythonMod(s, 2) ^ (2 * r(pythonDiv(s, 4)))
  }

  def main(args: Array[String]): Unit = {
    for(n <- 0 until 40) println(f(n))
    val distinctLists = (0 until 10000).map(f).toSet
    println(distinctLists.size)
  }
}

Answer 11

Python3, 242 bytes:

def f(n):
 d,D={},{}
 while n>1:
  k=0
  for i in range(2,n+1):
   if all(i%j for j in range(2,i)if i!=j):
    k+=1;D[i]=k
    if 0==n%i:d[i]=d.get(i,0)+1;n//=i
 return'+'.join(f'{(abs(T:=d[j])//2+1*T%2)*[-1,1][T%2]}*x^{D[j]-1}'for j in d)

Returns a pretty-printed polynomial for \$n\$.

Try it online!

Answer 12

Haskell, 95 bytes

import Data.List
f=nub$(dropWhile(<1))<$>concatMap(\n->(iterate(map(:)[-n..n]<*>)[[]])!!n)[0..]

iterate(map(:)[-n..n]<*>)[[]]!!n gets us {−n, …, n}ⁿ. Then we drop leading zeros and let nub do all the hard work.

Attempt This Online!

Answer 13

JavaScript (Node.js), 49 bytes

f=(n,i=0)=>n?n&1?f(n/2,(i<1)-i):[i,...f(n>>1)]:[]

Try it online!

JavaScript (Node.js), 52 bytes

f=(n,i=0)=>n?n&1?f(n/2,i+1):[n&2?~i:i,...f(n>>2)]:[]

Try it online!

Write index into binary and convert x011111 into one coefficient

zero is expressed as 00 so needn't extra check of remaining

Answer 14

BQN (CBQN), 55 bytes

{𝕩↑⍷∾{{⊑(𝕩=0)⊐0}⊸↓¨∾{⥊([⥊(↕𝕩)≍(-↕𝕩)])∾⌜⍟𝕩⋈⟨⟩}¨↕𝕩}¨↕𝕩+2}

This is a port of my Haskell answer. It's extremely slow.

Attempt This Online!