16
\$\begingroup\$

The Steenrod algebra is an important algebra that comes up in algebraic topology. The Steenrod algebra is generated by operators called "Steenrod squares," one exists for each positive integer i. There is a basis for the Steenrod algebra consisting of "admissible monomials" in the squaring operations. It is our goal to generate this basis.

A sequence of positive integers is called admissible if each integer is at least twice the next one. So for instance [7,2,1] is admissible because \$7 \geq 2*2\$ and \$2 \geq 2*1\$. On the other hand, [3,2] is not admissible because \$3 < 2*2\$. (In topology we would write \$\mathrm{Sq}^7 \mathrm{Sq}^2\mathrm{Sq}^1\$ for the sequence [7,2,1]).

The degree of a sequence is the total of it's entries. So for instance, the degree of [7,2,1] is \$7 + 2 + 1 = 10\$. The excess of an admissible sequence is the first element minus the total of the remaining elements, so [7,2,1] has excess \$7 - 2 - 1 = 4\$.

Task

Write a program that takes a pair of positive integers (d,e) and outputs the set of all admissible sequences of degree d and excess less than or equal to e. The output is a set so the order of the admissible sequences doesn't matter.

Examples:

 Input: 3,1
 Output: [[2,1]]

Here we are looking for admissible sequences with total 3. There are two options, [3] and [2,1]. ([1,1,1] and [1,2] have sum 3 but are not admissible). The excess of [3] is 3 and the excess of [2,1] is \$2-1 = 1\$. Thus, the only sequence with excess \$\leq1\$ is [2,1].

Input: 6, 6
Output: [[6], [5, 1], [4, 2]] (or any reordering, e.g., [[5,1],[4,2],[6]])

Since excess is always less than or equal to degree, we have no excess condition. Thus, we're just trying to find all admissible sequences of degree 6. The options are [6], [5, 1], and [4, 2]. (These have excess \$6\$, \$5-1 = 4\$, and \$4-2=2\$.)

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

The admissible sequences of degree 10 are:

[[10], [9,1], [8,2], [7,3], [7,2,1], [6,3,1]]

These have excess \$10\$, \$9-1 = 8\$, \$8-2 = 6\$, \$7-3 = 4\$, \$7-2-1 = 4\$, and \$6-3-1=2\$ respectively, so the last three all work.

Scoring

This is code golf: Shortest solution in bytes wins.

Test cases:

Any reordering of the output is equally good, so for input (3, 3), outputs [[3],[2,1]] or [[2,1],[3]] are equally acceptable (however [[1,2],[3]] isn't).

Input: 1, 1
Output: [[1]]

Input: 3, 3
Output: [[2,1], [3]]

Input: 3, 1
Output: [[2,1]]

Input: 6, 6
Output: [[6], [5, 1], [4, 2]]

Input: 6, 4
Output: [[5,1], [4,2]]

Input: 6, 1
Output: []

Input: 7, 7
Output: [[7], [6,1], [4,2,1], [5,2]]

Input: 7,1
Output: [[4,2,1]]

Input: 10, 10
Output: [[10], [9,1], [7,2,1], [6,3,1], [8,2], [7,3]]

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

Input: 26, 4
Output: [15, 7, 3, 1]

Input: 26, 6
Output: [[16, 7, 2, 1], [16, 6, 3, 1], [15, 7, 3, 1], [16, 8, 2], [16, 7, 3]]
\$\endgroup\$
  • 1
    \$\begingroup\$ Okay, I will provide a brief explanation. \$\endgroup\$ – Hood Jun 5 at 15:51

11 Answers 11

6
\$\begingroup\$

05AB1E, 16 12 bytes

Saved 4 bytes thanks to Grimy

Åœíʒx¦@P}ʒÆ@

Try it online!

Explanation

Ŝ              # integer partitions
  í             # reverse each
   ʒ    }       # filter, keep only elements true under:
    x           # each element doubled
     ¦          # remove the first element in the doubled list
      @         # compare with greater than or equal with the non-doubled
       P        # product
         ʒ      # filter, keep only elements true under:
          Æ     # reduce by subtraction
           @    # compare with greater than or equal to second input
\$\endgroup\$
  • \$\begingroup\$ ćsO- is the built-in Æ. \$\endgroup\$ – Grimmy Jun 6 at 10:54
  • \$\begingroup\$ Also À@¨ can be ¦@. \$\endgroup\$ – Grimmy Jun 6 at 13:14
  • 1
    \$\begingroup\$ @Grimy: Oh wow, how did I miss that :) Thank you! \$\endgroup\$ – Emigna Jun 6 at 14:43
5
\$\begingroup\$

Wolfram Language (Mathematica), 67 62 bytes

Cases[IntegerPartitions@#,a_/;2a[[1]]-#<=#2>Max@Ratios@a<=.5]&

Try it online!

-4 bytes by @attinat

  • IntegerPartitions@d : Get all lists of integers summing to d
  • Cases[,...]: Filter by the following condition:
    • 2#& @@# - d <= e &&: Twice the first element minus the sum is less than e, and...
    • Max@Ratios@#<=.5: Ratios of successive elements of the list are all less than 1/2.

Because e is less than .5, we can turn this into a chained inequality.

For a few extra bytes, this is significantly faster: Try it online!

\$\endgroup\$
5
\$\begingroup\$

Jelly,  16  15 bytes

-1 thanks to Erik the Outgolfer (a smart adjustment to the checking allowing a single filter)

:Ɲ;_/>¥’Ạ
ŒṗUçƇ

A dyadic link accepting a positive integer, d, on the left and a positive integer, e, on the right which yields a list of lists of positive integers.

Try it online! (the footer formats the results to avoid list the implicit list formatting Jelly does as a full program)

How?

:Ɲ;_/>¥’Ạ - Link 1: admissible and within excess limit? descending list, L; excess limit, e
 Ɲ        - neighbour-wise:
:         -   integer division  -- admissible if all these are >1
      ¥   - last two links as a dyad - i.e. f(L,e):
    /     -   reduce (L) by:
   _      -     subtraction
     >    -   greater than (e)? (vectorises)  -- within excess if all these are ==0
  ;       - concatenate
       ’  - decrement (vectorises)
        Ạ - all (non-zero)?

ŒṗUçƇ - Main link: integer, d; integer, e
Œṗ    - partitions (of d)
  U   - reverse each
    Ƈ - filter keep those (v in that) for which:
   ç  -   call last Link (1) as a dyad - i.e. f(v, e)
\$\endgroup\$
  • \$\begingroup\$ You can save a byte with a clever trick. It may take a little while to understand why that works. :P \$\endgroup\$ – Erik the Outgolfer Jun 5 at 23:16
  • \$\begingroup\$ @EriktheOutgolfer awesome, I had tried some similar ways to inline the two filters (including concatenation), but everything was coming out as 16 since I did not think of employing the decrement trick at the same time. \$\endgroup\$ – Jonathan Allan Jun 6 at 13:53
4
\$\begingroup\$

Haskell, 59 58 54 bytes

1 byte saved thanks to nimi

4 bytes saved thanks to xnor

0#_=[[]]
d#m=do i<-[1..div(m+d)2];(i:)<$>(d-i)#(2*i-d)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save some bytes by defining # directly: Try it online! \$\endgroup\$ – xnor Jun 7 at 3:11
3
\$\begingroup\$

JavaScript (V8),  88 87  81 bytes

Takes input as (e)(d). Prints the sequences to STDOUT.

e=>g=(d,s=x=d,a=[])=>s>0?d&&g(d-1,s,a,g(d>>1,s-d,[...a,d])):a[s]*2-x<=e&&print(a)

Try it online!

Commented

e =>                  // e = maximum excess
  g = (               // g is a recursive function taking:
    d,                //   d   = expected degree; actually used as the next candidate
                      //         term of the sequence in the code below
    s =               //   s   = current sum, initialized to d; we want it to be equal
                      //         to 0 when a sequence is complete
    x = d,            //   x   = copy of the expected degree
    a = []            //   a[] = current sequence
  ) =>                //
    s > 0 ?           // if s is positive:
      d &&            //   if d is not equal to 0:
        g(            //     outer recursive call:
          d - 1,      //       decrement d
          s,          //       leave s unchanged
          a,          //       leave a[] unchanged
          g(          //       inner recursive call:
            d >> 1,   //         update d to floor(d / 2)
            s - d,    //         subtract d from s
            [...a, d] //         append d to a[]
          )           //       end of inner recursive call
        )             //     end of outer recursive call
    :                 //   else:
      a[s] * 2 - x    //     s if either 0 (success) or negative (failure)
                      //     if s is negative, a[s] is undefined and this expression
                      //     evaluates to NaN, forcing the test to fail
      <= e            //     otherwise, we test whether the excess is valid
      && print(a)     //     and we print a[] if it is
\$\endgroup\$
3
\$\begingroup\$

Pyth, 23 bytes

f!>-FTvzf!<#2/MCtBT_M./

Try it online!

f!>-FTvzf!<#2/MCtBT_M./Q   Implicit: Q=input 1, vz=input 2
                           Trailing Q inferred
                     ./Q   Generate partitions of Q (ordered lists of integers which sum to Q)
                   _M      Reverse each
        f                  Filter keep elements of the above, as T, where:
               CtBT          Pair the set with itself without the first element and transpose
                             This yields all adjacent pairs of values
             /M              Integer divide each pair
           #                 Filter keep elements...
          < 2                ... less than 2
                             For admissible sequences this will be empty
         !                   Logical NOT - maps [] to true, populated lists to false
                           Result of filter are all admissible sequences
f                          Filter keep the above, as T, where:
   -FT                       Reduce T by subtraction to get degree
 !>   vz                     Is the above not greater than vz?
                           Implicit print
\$\endgroup\$
3
\$\begingroup\$

Python 3, 213 bytes

Giant list comprehension. Most likely not the best way to do this, but I can't figure out how to skip the if statements

import itertools as z
f=lambda d,e:[c for c in [[b for b in list(z.permutations(range(1,d+1),i)) if sum(b)==d and b[0]-sum(b[1:i])<=e and all([b[i]>=b[i+1]*2 for i in range(len(b)-1)])] for i in range(1,5)] if c]

Python 3, 172 bytes

from itertools import*
r=range
f=lambda d,e:filter(len,[[b for b in permutations(r(1,d+1),i)if d==sum(b)and~e<d-2*b[0]and all(i>=j*2for i,j in zip(b,b[1:]))]for i in r(5)])

Try it online!

As according to edits by @Jonas Ausevicius

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to the site. A few tips: I looks like you are not super familiar with where spacing is required in python. You have a couple of places that spaces could be removed just fine, so I would look into that. Also functions like all can take a generator so you can just do all(...) instead of all([...]). Lastly since your submission is a completely anonymous function you are not penalized for the assignment (f=) and thus can deduct it from your score (-2 bytes). \$\endgroup\$ – Wheat Wizard Jun 5 at 15:23
  • \$\begingroup\$ With those changes your answer is down to 201 bytes \$\endgroup\$ – Wheat Wizard Jun 5 at 15:23
  • \$\begingroup\$ Oh and also in python3 you can cast to list with [*(...)] instead of list(...) which usually saves a byte but in your case saves 2 since it also allows you to remove a space. \$\endgroup\$ – Wheat Wizard Jun 5 at 15:25
  • 2
    \$\begingroup\$ 189 bytes if it's fine to return a filter object, otherwise 192 with [*filter(...)]. Also welcome :) \$\endgroup\$ – Reinstate Monica Jun 5 at 15:57
  • 2
    \$\begingroup\$ 172 bytes \$\endgroup\$ – Jonas Ausevicius Jun 6 at 9:23
2
\$\begingroup\$

Charcoal, 42 bytes

Fθ⊞υ⟦⊕ι⟧FυF…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ιIΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Try it online! Link is to verbose version of code. Explanation:

Fθ⊞υ⟦⊕ι⟧

First create a list of lists from [1]..[d].

FυF…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ι

For each list create new lists by prefixing all the numbers from the doubled first number up to d and append those lists to the list of lists to be processed. This ensures that all admissible sequences containing numbers not greater than d are created.

IΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Output only those lists whose degree is d and excess is not greater than e. (The sum of the degree and excess is equal to twice the first number of the list.)

\$\endgroup\$
2
\$\begingroup\$

Python 3, 156 bytes

lambda d,e:[x for y in range(5)for x in permutations(range(1,d+1),y)if all(i>=j*2for i,j in zip(x,x[1:]))and d==sum(x)and~e<d-2*x[0]]
from itertools import*

takes d,e as input; outputs list of tuples

Similar to @OrangeCherries answer and help from comments; but more bytes saved

Try it online!

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

Jelly, 18 bytes

ŒṗU:Ɲ’ẠƊƇUṪ_SƊ’<ʋƇ

Try it online!

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

Ruby, 78 bytes

g=->(d,e,m=1){d<m ?[]:g[d-m,e+m,m*2].map{|q|q+[m]}+g[d,e,m+1]|(d>e ?[]:[[d]])}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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