14
\$\begingroup\$

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 the shortest program (per language) wins.
\$\endgroup\$
5
  • \$\begingroup\$ I don't think this is a duplicate. \$\endgroup\$
    – alephalpha
    Jul 23, 2023 at 9:32
  • 2
    \$\begingroup\$ May we output coefficients in the opposite order, with constant term on the left? \$\endgroup\$
    – xnor
    Jul 23, 2023 at 22:08
  • \$\begingroup\$ Are we allowed to use the empty string to represent zero as a coefficient within a list of coefficients, e.g. 1,,2 to represent 1*x^2+0*x+2? \$\endgroup\$
    – DLosc
    Jul 26, 2023 at 20:42
  • \$\begingroup\$ @DLosc I will not override the default format for numbers. This means that the empty string can only be used to represent zero if it is your languages natural representation for zero. \$\endgroup\$
    – bsoelch
    Jul 27, 2023 at 7:45
  • \$\begingroup\$ @bsoelch That makes sense. Figured it wouldn't hurt to ask. :) \$\endgroup\$
    – DLosc
    Jul 27, 2023 at 16:53

14 Answers 14

11
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Nice one! You can save one, trivially, by reversing the order of representation. I.e. use for*t,h in etc. \$\endgroup\$
    – loopy walt
    Jul 23, 2023 at 21:55
  • \$\begingroup\$ This is a nice method! h<1 saves one. \$\endgroup\$ Jul 24, 2023 at 2:47
9
\$\begingroup\$

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

\$\endgroup\$
4
  • 2
    \$\begingroup\$ No need for the or[0] if you just stipulate there are no trailing zero coefficients. \$\endgroup\$ Jul 23, 2023 at 16:37
  • \$\begingroup\$ I just wasn't sure whether it is ok to represent 0 by an empty coefficient list. I guess one could argue either way. Or is there some relevant meta I'm not aware of? \$\endgroup\$
    – loopy walt
    Jul 23, 2023 at 16:56
  • 2
    \$\begingroup\$ You are already representing a polynomial as a list of coefficients without trailing zeros (i.e. \$3x^2\$ is [0,0,3] rather than [0,0,3,0,0,...,0,...]), so there should be no need to special case the zero polynomial. \$\endgroup\$ Jul 23, 2023 at 17:08
  • \$\begingroup\$ @JonathanAllan By the same token one could argue that base 10 (or anything) integers are represented without leading zeros, yet, for example, Python does not accept the empty string to represent 0. \$\endgroup\$
    – loopy walt
    Jul 23, 2023 at 21:03
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Can you not vectorise -1ᵉe to avoid having to use ? \$\endgroup\$
    – Neil
    Jul 24, 2023 at 5:36
  • \$\begingroup\$ Yes, but it's the same byte count (unless I've missed a trick of course) since it will need the ÆE result on both sides: ÆE-*×Ɗ:2. \$\endgroup\$ Jul 24, 2023 at 14:04
6
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ The d is unnecessary. (Jelly seems to need it because it can't easily negate x x times.) \$\endgroup\$
    – Neil
    Jul 23, 2023 at 22:19
  • \$\begingroup\$ Oh yeah, thanks @Neil \$\endgroup\$
    – The Thonnu
    Jul 24, 2023 at 2:00
3
\$\begingroup\$

Charcoal, 56 53 51 31 bytes

≔IE⮌⍘N²ιθWθ«≔Φι﹪λ²θ⟦I↨⮌Φι¬﹪λ²±²

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

≔IE⮌⍘N²ιθ

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

Wθ«

Repeat until there are no more terms of the polynomial.

≔Φι﹪λ²θ

Remove the current term from the value.

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

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:

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

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

≔⮌↨N²θ

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

Wθ«

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.

»∨Φ⪫⮌Eυ⎇ι⁺⎇∨¬κ⊖↔ι﹪%+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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Vyxal r, 36 bitsv2, 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.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ ∆ǏƛÞni Why calculate when you have the necessary thing built-in :P \$\endgroup\$
    – Bubbler
    Jul 24, 2023 at 4:49
  • 2
    \$\begingroup\$ @Bubbler well you see that's because I forgot it existed :p \$\endgroup\$
    – lyxal
    Jul 24, 2023 at 5:38
2
\$\begingroup\$

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)
  }
}
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ suggest getting rid of if i!=j in line 6 as j < i \$\endgroup\$
    – c--
    Jul 23, 2023 at 21:13
2
\$\begingroup\$

Haskell, 96 bytes

import Data.List
f=nub$(dropWhile(==0))<$>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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

BQN (CBQN), 55 bytes

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

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

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.