title: Is the matrix rank-one?

text:
# Question
Title: Is the matrix rank-one?
Given a matrix of integers, test if it's rank-one, meaning that every row is a multiple of the same vector. For example, in

```
 2   0  -20  10
-3   0   30 -15
 0   0   0   0

```

every row is a multiple of `1 0 -10 5`.

The same definition also works with columns in place of rows. Alternatively, a matrix is rank-one if it's like a multiplication table:

```
 *    1   0  -10  5
    ----------------
 2 |  2   0  -20  10
-3 | -3   0   30 -15
 0 |  0   0   0   0

```

We've assigned row labels `r[i]`and column labels `c[j]` so that each matrix entry `M[i][j]` is the product of the corresponding labels as `M[i][j] = r[i] * c[j]`.

**Input:**

An integer matrix as a 2D container of your choice. For example, a list of lists, a 2D array, or similar. You shouldn't take the width or height as additional inputs unless the array format requires it.

The matrix may be non-square. It will have at least one nonzero entry -- you don't have to deal with empty or zero matrices.

You can assume the integers won't cause overflow issues.

**Output:**

A consistent value for rank-one matrices, and a different consistent value for other matrices.

**Built-ins:**

You *may not* use any built-in to computes rank or directly check rank one. You may use other built-ins like eigenvalues, decompositions, etc, but I encourage upvoting answers that don't have built-ins do most of the work.

**Test cases:**

Rank-one:

```
[[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]
[[0, 0, 0], [0, 3, 0], [0, 0, 0]]
[[-10]]
[[0, 0, 0], [0, 4, 11], [0, -4, -11]]

```

Not rank-one:

```
[[-2, 1], [2, 4]]
[[0, 0, 3], [-22, 0, 0]]
[[1, 2, 3], [2, 4, 6], [3, 6, 10]]
[[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]

```

**Leaderboard:**

```
var QUESTION_ID=143528,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/143528/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# Jelly, 6 bytes

```
ẸÐfÆrE

```

Try it online!

### How it works

```
ẸÐfÆrE  Main link. Argument: M (2D array)

ẸÐf     Filter by any, removing rows of zeroes.
   Ær   Interpret each row as coefficients of a polynomial and solve it over the
        complex numbers.
     E  Test if all results are equal.

```

### Precision

`Ær` uses numerical methods, so its results are usually inexact. For example, the input **\[6, -5, 1\]**, which represents the polynomial **6 - 5x + x²**, results in the roots **3.0000000000000004** and **1.9999999999999998**. However, multiplying all coefficients of a polynomial by the same non-zero constant results in equally inexact roots. For example, `Ær` obtains the same roots for **\[6, -5, 1\]** and **\[6 × 10100, -5 × 10100, 10100\]**.

It should be noted that the limited precision of the *float* and *complex* types **can** lead to errors. For example, `Ær` would obtain the same roots for **\[1, 1\]** and **\[10100, 10100 \+ 1\]**. Since we can assume the matrix is not large and not specifically chosen to be misclassified, that should be fine.
> 14 votes

# Answer
# Haskell, 50 bytes

`r` takes a list of lists of `Integer`s and returns `False` if the matrix has rank one, `True` otherwise.

```
r l=or[map(x*)b<map(y*)a|a<-l,b<-l,(x,y)<-zip a b]

```

Try it online!

# How it works

* Generates all pairs of rows `a` and `b` (including equal rows), and for each pair, lets `x` and `y` run through corresponding elements.
* Multiplies the row `b` by `x` and the row `a` by `y`. The matrix will have rank one if and only if the results are always equal.
* Since pairs are generated in both orders, `<` can be used to check if there's ever an inequality. The list of test results are combined with `or`, giving `True` if there are any non-proportional rows.
> 8 votes

# Answer
# Mathematica, ~~51~~ 33 bytes

```
RowReduce@#~Count~Except@{0..}<2&

```

**Input**

> \[{{2,0,-20,10},{-3,0,30,-15},{0,0,0,0}}\]

*-14 bytes from user202729*
3 more bytes saved from junghwanmin
> 7 votes

# Answer
# JavaScript (ES6), ~~68~~ ~~67~~ 65 bytes

This one is based on Neil's 05AB1E answer and is significantly more efficient than my original approach.

Returns `false` for rank-one and `true` otherwise.

```
f=(a,R,V,X)=>a.some(r=>r.some((v,x)=>R?v*V-r[X]*R[x]:f(a,r,v,x)))

```

### Test cases

```
f=(a,R,V,X)=>a.some(r=>r.some((v,x)=>R?v*V-r[X]*R[x]:f(a,r,v,x)))

console.log(f([[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]))
console.log(f([[0, 0, 0], [0, 3, 0], [0, 0, 0]]))
console.log(f([[-10]]))
console.log(f([[0, 0, 0], [0, 4, 11], [0, -4, -11]]))

console.log(f([[-2, 1], [2, 4]]))
console.log(f([[0, 0, 3], [-22, 0, 0]]))
console.log(f([[1, 2, 3], [2, 4, 6], [3, 6, 10]]))
console.log(f([[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]))
```

---

# Original answer, 84 bytes

Returns `false` for rank-one and `true` otherwise.

```
a=>a.some(r=>r.some((x,i)=>(isNaN(x/=a.find(r=>r.some(x=>x))[i])?r:1/r[0]?r=x:x)-r))

```

### Test cases

```
let f =

a=>a.some(r=>r.some((x,i)=>(isNaN(x/=a.find(r=>r.some(x=>x))[i])?r:1/r[0]?r=x:x)-r))

console.log(f([[2, 0, -20, 10], [-3, 0, 30, -15], [0, 0, 0, 0]]))
console.log(f([[0, 0, 0], [0, 3, 0], [0, 0, 0]]))
console.log(f([[-10]]))
console.log(f([[0, 0, 0], [0, 4, 11], [0, -4, -11]]))

console.log(f([[-2, 1], [2, 4]]))
console.log(f([[0, 0, 3], [-22, 0, 0]]))
console.log(f([[1, 2, 3], [2, 4, 6], [3, 6, 10]]))
console.log(f([[0, -2, 0, 0], [0, 0, 0, 1], [0, 0, -2, 0]]))
```

### How?

```
a => a.some(r =>          // given a matrix a, for each row r of a:
  r.some((x, i) =>        //   for each value x of r at position i:
    (                     //
      isNaN(x /=          //     divide x by a[ref][i]
        a.find(r =>       //       where ref is the index of the first row that
          r.some(x => x)  //       contains at least one non-zero value
        )[i]              //       (guaranteed to exist by challenge rules)
      ) ?                 //     we get NaN for 0/0, in which case:
        r                 //       use r, so that this column is ignored
      :                   //     else:
        1 / r[0] ?        //       if r is still holding the current row:
          r = x           //         set it to x (either a float, +Inf or -Inf)
        :                 //       else:
          x               //         use x
    ) - r                 //     subtract r from the value set above (see table)
  )                       //   end of some()
)                         // end of every()

```

The subtraction which is performed at the end of the code can lead to many different situations, which are summarized below:

```
A                   | B              | A - B       | False / True
--------------------+----------------+-------------+-------------
array of 1 number   | same array     | 0           | False
array of 2+ numbers | same array     | NaN         | False
a number            | same number    | 0           | False
+Infinity           | +Infinity      | NaN         | False
-Infinity           | -Infinity      | NaN         | False
a number            | another number | <> 0        | True
+Infinity           | -Infinity      | +Infinity   | True
-Infinity           | +Infinity      | -Infinity   | True
a number            | +/-Infinity    | +/-Infinity | True
+/-Infinity         | a number       | +/-Infinity | True

```

The test fails as soon as we get a truthy value: this happens when we encounter two distinct ratios (other than ***0 / 0***) between ***a(i,y)*** and ***a(i,r)*** in any row ***y*** of the matrix, where ***r*** is the index of a non-zero row.
> 4 votes

# Answer
# 05AB1E, ~~16~~ 13 bytes

```
2ãεø2ãε`R*E]W

```

Try it online! Uses the multiplication table property that the opposite corners of any rectangle have the same product. Edit: Saved 3 bytes thanks to @KevinCruijssen. Explanation:

```
2ãε             Loop over each pair of rows
   ø            Transpose the pair into a row of pairs
    2ãε         Loop over each pair of columns
       `R*E     Cross-multiply and check for equality
           ]W   All results must be true

```
> 4 votes

# Answer
# Python 2 \+ numpy, 58 bytes

```
lambda m:sum(linalg.svd(m)[1]>1e-10)==1
from numpy import*

```

Try it online!

Credit to this.
> 3 votes

# Answer
# Jelly, 12 bytes

```
ẸÐfµ÷"Ð€ZE€Ẹ

```

Try it online!

# Explanation

```
ẸÐfµ÷"Ð€ZE€Ẹ  Main link
 Ðf           Filter; keep all elements where
Ẹ             At least one element is truthy (remove zero-rows)
      Ð€      For each row on the right side
    ÷"        Divide it by each row in the original
        Z     Zip the array
          €   For each submatrix
         E    Are all rows equal?
           Ẹ  Is at least one of the elements from above truthy?

```

Explanation may be slightly incorrect as this is my interpretation of miles's golf of my original algorithm

-5 bytes thanks to miles
> 3 votes

# Answer
# TI-Basic (TI-83 series), ~~28~~ ~~27~~ 28 bytes (62 characters)

```
:Prompt [A]
:{0→X
:Matr►list(ref([A])ᵀ,L₁,X
:not(max(abs(ᶫX

```

Computes the row-echelon form of the matrix `[A]`, stores its first row (to be discarded) in `L₁` and its second row in `ᶫX`. Then `max(abs(ᶫX` will be zero if `ᶫX` consists only of zeroes, and a positive value otherwise, which `not(` changes to 1 if the matrix is rank one, 0 otherwise.

For a 1-row matrix, `ᶫX` is set to `{0}` and then doesn't get changed when we try to look at the nonexistent second row of the matrix.

---

*-1 byte thanks to Scott Milner*

*+1 byte to fix dimension error for 1-row matrices. Turns out the* `Matr►list(` *command complains if you try to extract the second row from a matrix with only one row; however, if you try to extract the first and second row both from the matrix, it will fail silently.*
> 3 votes

# Answer
# Brachylog, 27 bytes

```
{⊇Ċ}ᶠzᵐ{↰₁ᶠ{⟨hz{t↔}⟩×ᵐ=}ᵐ}ᵐ

```

Try it online!

Uses Neil's approach of "products of opposite corners of each rectangle should be equal". Cross product is costly and takes 10 whole bytes, but this is still shorter than any division based approach I tried, mainly because of the stipulation of two consistent outputs for truthy and falsey in the question - making falsey be only a `false.`, and not sometimes a divide-by-zero error, uses too many bytes.

```
{⊇Ċ}ᶠzᵐ{↰₁ᶠ{⟨hz{t↔}⟩×ᵐ=}ᵐ}ᵐ
{⊇Ċ}ᶠ                        Get each pair of rows from the matrix
                             eg.: [ [[a, b, c], [k, l, m]], ... ]
     zᵐ                      Zip each pair's elements
                                  [ [[a, k], [b, l], [c, m]], ... ]
       {                 }ᵐ  Map this over each pair of rows:
                                  [[a, k], [b, l], [c, m]]
        ↰₁ᶠ                  Get each pair of paired elements from the rows
                                  [[[a, k], [b, l]], [[b, l], [c, m]], [[a, k], [c, m]]]
           {           }ᵐ    Map this over each pair of pairs
                                  [[a, k], [b, l]]
            ⟨hz{t↔}⟩         Zip the first pair with the reverse of the second
                                  [[a, l], [k, b]]
                    ×ᵐ       Multiply within each sublist
                                  [al, kb]
                      =      The results should be equal
                             (If the results are unequal for any pair, the whole predicate fails,
                              and outputs false.)

```

Alternate approach based on element-wise division (**30 bytes**):

```
{≡ᵉ¬0&}ˢ\↰₁ˢ{c×¬0&⟨hz∋⟩ᶠ/ᵐ²=ᵐ}

```

Try it online!
> 3 votes

# Answer
# Jelly, 9 bytes

```
ẸÐf÷g/$€E

```

Try it online!

```
ẸÐf         Discard zero rows
   ÷  $€    Divide each row by
    g/        its greatest common divisor
        E   Does this list have only one unique element?

```
> 2 votes

# Answer
## SageMath, 40 bytes

```
lambda M:any(M.rref()[1:])*(M.nrows()>1)

```

Try it online

This anonymous function returns `False` if the matrix is rank-one, and `True` otherwise.

The function takes a matrix `M` as input, converts it to reduced row-echelon form (`M.rref()`), and tests for `any` of the rows past the first being non-zero. Then, that value is multiplied by `M.nrows()>1` (does the matrix have more than one row?).
> 1 votes

# Answer
# Python 3, ~~93~~  91 bytes

```
lambda m,e=enumerate:any(h*g-r[j]*s[i]for r in m for i,h in e(r)for s in m for j,g in e(s))

```

Try it online!

*How it works*

Checks if any 2-minor has nonzero determinant. If this is the case the rank must be at least 2: "A non-vanishing p-minor (p × p submatrix with non-zero determinant) shows that the rows and columns of that submatrix are linearly independent, and thus those rows and columns of the full matrix are linearly independent (in the full matrix), so the row and column rank are at least as large as the determinantal rank" (from Wikipedia)

Note: shaved two bytes thanks to user71546's comment.
> 1 votes

# Answer
# Pari/GP, 18 bytes

```
a->#matimage(a)==1

```

`matimage` gives a basis of the image of the linear transformation defined by the matrix.

Try it online!
> 0 votes

# Answer
# Scala, 86 bytes

Golfed version. Try it online!

```
l=>l.exists(a=>l.exists(b=>a.zip(b).exists{case(x,y)=>b.map(_*x).sum<a.map(_*y).sum}))

```

Ungolfed version. Try it online!

```
object Main extends App {
  val lists = List(
    List(List(2, 0, -20, 10), List(-3, 0, 30, -15), List(0, 0, 0, 0)),
    List(List(0, 0, 0), List(0, 3, 0), List(0, 0, 0)),
    List(List(-10)),
    List(List(0, 0, 0), List(0, 4, 11), List(0, -4, -11)),
    List(List(-2, 1), List(2, 4)),
    List(List(0, 0, 3), List(-22, 0, 0)),
    List(List(1, 2, 3), List(2, 4, 6), List(3, 6, 10)),
    List(List(0, -2, 0, 0), List(0, 0, 0, 1), List(0, 0, -2, 0))
  )

  lists.foreach { list =>
    println(s"$list: ${r(list)}")
  }

  def r(list: List[List[Int]]): Boolean = {
    list.exists { a =>
      list.exists { b =>
        a.zip(b).exists { case (x, y) =>
          b.map(_ * x).sum < a.map(_ * y).sum
        }
      }
    }
  }
}

```
> 0 votes

---
Tags: code-golf, decision-problem, matrix, linear-algebra
---


# Question
Title: Longest sequence of Egyptian fractions with n as denominator
#### Background

From Wikipedia: An Egyptian fraction is the sum of distinct unit fractions. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. The value of an expression of this type is a positive rational number a/b. Every positive rational number can be represented by an Egyptian fraction.

#### Task

Write a function that given \\$ n \\$, outputs the longest sequence of Egyptian fractions (that sum up to 1) where \\$ n \\$ is the largest denominator.

#### Rules

* If no solution exists, you may output anything or nothing except any real number
* If there are two or more solutions, output any one of them
* Assume \\$ n \\$ is not two and is a natural number
* Your output must be in descending order
* You must not output duplicates
* Each individual fraction must be separated by a plus symbol (`+`). Spaces are optional. However the plus symbol should not come after the last fraction.
* Your code does not need to practically handle very high \\$ n \\$, but it must work in theory for all \\$ n \\$ for which a solution exists
* You may use any standard I/O method
* Standard loopholes are forbidden

#### Examples

`6``1/2 + 1/3 + 1/6`

`15``1/3 + 1/4 + 1/6 + 1/10 + 1/12 + 1/15`

`20`:

```
1/4 + 1/5 + 1/6 + 1/9 + 1/10 + 1/15 + 1/18 + 1/20

```

or

```
1/3 + 1/5 + 1/9 + 1/10 + 1/12 + 1/15 + 1/18 + 1/20

```

`2016`:

```
1/15 + 1/22 + 1/24 + 1/25 + 1/30 + 1/32 + 1/33 + 1/39 + 1/40 + 1/42 + 1/44 + 1/45 + 1/48 + 1/55 + 1/56 + 1/60 + 1/63 + 1/64 + 1/65 + 1/66 + 1/70 + 1/72 + 1/78 + 1/80 + 1/84 + 1/85 + 1/88 + 1/90 + 1/91 + 1/96 + 1/99 + 1/104 + 1/110 + 1/112 + 1/119 + 1/120 + 1/130 + 1/132 + 1/135 + 1/136 + 1/150 + 1/154 + 1/156 + 1/160 + 1/165 + 1/168 + 1/170 + 1/171 + 1/175 + 1/180 + 1/182 + 1/184 + 1/189 + 1/190 + 1/195 + 1/198 + 1/200 + 1/208 + 1/210 + 1/220 + 1/225 + 1/230 + 1/238 + 1/240 + 1/260 + 1/270 + 1/272 + 1/275 + 1/288 + 1/299 + 1/300 + 1/306 + 1/320 + 1/324 + 1/325 + 1/330 + 1/340 + 1/345 + 1/368 + 1/400 + 1/405 + 1/434 + 1/459 + 1/465 + 1/468 + 1/476 + 1/480 + 1/495 + 1/496 + 1/527 + 1/575 + 1/583 + 1/672 + 1/765 + 1/784 + 1/795 + 1/810 + 1/840 + 1/875 + 1/888 + 1/900 + 1/918 + 1/920 + 1/975 + 1/980 + 1/990 + 1/1000 + 1/1012 + 1/1050 + 1/1088 + 1/1092 + 1/1100 + 1/1104 + 1/1113 + 1/1125 + 1/1196 + 1/1200 + 1/1224 + 1/1258 + 1/1309 + 1/1330 + 1/1386 + 1/1395 + 1/1425 + 1/1440 + 1/1470 + 1/1480 + 1/1484 + 1/1488 + 1/1512 + 1/1620 + 1/1650 + 1/1680 + 1/1728 + 1/1729 + 1/1800 + 1/1824 + 1/1836 + 1/1840 + 1/1848 + 1/1850 + 1/1870 + 1/1890 + 1/1950 + 1/1980 + 1/1995 + 1/2000 + 1/2016

```

or

```
...

```

#### Criteria

1. For first place: shortest code in bits wins
2. For second place: fastest code wins.

So if a code is the shortest and fastest, the second fastest code will be given 2nd place

P.S: The background definition and some rules are taken from this and this question respectively.

# Answer
> 1 votes
# Vyxal `R`, 89 bitsv2, 11.125 bytes

```
ṗ't?=;Ė'∑1=;t\+j

```

Try it Online!

+~3 bytes due to reading the specs

Me when when fraction type automatically. Powerset is sorted by length by default, so the last item is guaranteed to be the longest.

# Answer
> 2 votes
# JavaScript (ES6), 103 bytes, \\$O(2^n)\\$

Returns an empty string if there's no solution.

```
f=(n,a=o=[],p=0,q=1)=>n?f(n-1,["1/"+n,...a],p*n+q,q*n,p&&f(n-1,a,p,q))&&o.join`+`:o=p-q|o[a.length]?o:a

```

Try it online!

# Answer
> 2 votes
# Charcoal, 50 bytes, *O(2ⁿ)*

```
Ｎθ≔ΦＥ…Ｘ²⊖θＸ²θ⊕⌕Ａ⮌⍘ι²1⁼ΠιΣ÷Πιιυ¿υ⪫⁺1/Ｉ§υ⌕ＥυＬι⌈ＥυＬι+

```

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

```
Ｎθ

```

Input `n`.

```
≔ΦＥ…Ｘ²⊖θＸ²θ⊕⌕Ａ⮌⍘ι²1⁼ΠιΣ÷Πιιυ

```

Get the powerset of `[1..n-1]` and see which sets' reciprocals sum to `1` when `1/n` is included.

```
¿υ⪫⁺1/Ｉ§υ⌕ＥυＬι⌈ＥυＬι+

```

If any were found then output the longest.

53 bytes for a version that is twice as fast because it gets the powerset of `[2..n-1]`:

```
Ｎθ≔ΦＥ⊗…Ｘ²⁻θ²Ｘ²⊖θ⊕⌕Ａ⮌⍘ι²1⁼ΠιΣ÷Πιιυ¿υ⪫⁺1/Ｉ§υ⌕ＥυＬι⌈ＥυＬι+

```

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

~~71~~ 66 bytes for an algorithm that is slightly faster because it stops considering fractions once the sum exceeds `1` (I don't know how this affects the time complexity though):

```
Ｎθ≔⟦⟦θ⟧⟧ηＦ…²θＦ⮌η«≔⁺κ⟦ι⟧κ≔⁻Σ÷ΠκκΠκζ¿‹ζ⁰⊞ηκ¿∧¬ζ›ＬκＬυ≔⊞ＯΦκμθυ»⪫⁺1/Ｉυ+

```

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

```
Ｎθ≔⟦⟦θ⟧⟧η

```

Input `n` and start with `1/n` as a required fraction.

```
Ｆ…²θＦ⮌η«

```

For each integer from `2` to `n-1`, loop over all of the sets so far.

```
≔⁺κ⟦ι⟧κ≔⁻Σ÷ΠκκΠκζ

```

Create a new set containing the current integer and calculate the excess of the sum of reciprocals.

```
¿‹ζ⁰⊞ηκ

```

If the excess is negative i.e. the sum is less than `1` then add this to the list of sets to check next iteration.

```
¿∧¬ζ›ＬκＬυ≔⊞ＯΦκμθυ

```

If the excess is zero i.e. the sum is `1` and this set is longer than any previously found set then set this as the longest found set so far.

```
»⪫⁺1/Ｉυ+

```

Output the longest set found.

# Answer
> 2 votes
# Python3, 246 bytes:

```
def f(n):
 q,t=[([*range(2,n)],[],1-(1/n))],[]
 while q:
  d,c,r=q.pop(0)
  if[]==d:continue
  if round(r,5)==0:t+=[c];continue
  if(U:=r-(1/d[0]))>=0:q+=[(d[1:],c+[d[0]],U)]
  q+=[(d[1:],c,r)]
 return'+'.join(f'1/{i}'for i in max(t,key=len)+[n])

```

Try it online!

# Answer
> 1 votes
# Excel, 168 bytes, \\$O(2^n)\\$

```
=LET(
    a,SEQUENCE(,A1),
    b,IF(MOD(INT(SEQUENCE(2^A1,,0)/2^(a-1)),2),1/a,),
    IFERROR(TEXTJOIN("+",,
        "1/"&TOCOL(1/TAKE(FILTER(b,TAKE(b,,-1)*(MMULT(b,TOCOL(a^0))=1)),-1),2))
    ,"")
)

```

Input in cell `A1`.

# Answer
> 1 votes
# 05AB1E, ~~23~~ 22 bytes

```
LæʒIå}DzOT.òÏéθ„1/ì'+ý

```

Will output nothing if there are no results.

There is a bug in the filter builtin `ʒ` for decimals `1.0` (which should be 05AB1E-truthy). So the second filter `ʒ...Θ}` has been replaced with `D...Ï` for -1 byte, without changing its functionality.

Try it online or verify test cases until it times out.

**Explanation:**

```
L          # Push a list in the range [1, (implicit) input-integer]
 æ         # Get the powerset of this list
  ʒ  }     # Filter this list of lists by:
   Iå      #  It contains the input-integer
  D     Ï  # Filter it further by:
   z       #  Take 1/v for each value `v` in the list
    O      #  Sum them together
     T.ò   #  Round it to 10 decimal digits to account for floating point inaccuracies
           #  (only 1 is truthy in 05AB1E)
  é        # After the filters: sort the remaining list by length (shortest to longest)
   θ       # Pop and push the last/longest valid list
  „1/ì     # Prepend "1/" in front of each integer
      '+ý '# And join these strings with "+"-delimiter
           # (after which the resulting string is output implicitly as result)

```

# Answer
> 1 votes
# Scala, 345 bytes

Port of @Ajax1234's Python answer in Scala.

Golfed version. Try it online!

```
n=>{var q=Queue((2 to n-1 toList,List[Int](),1-1.0/n));var t=List[List[Int]]()
while(q.nonEmpty){val(d,c,r)=q.dequeue;if(d.nonEmpty){if(BigDecimal(r).setScale(5,BigDecimal.RoundingMode.HALF_UP).toDouble==0)t=c::t
val u=r-1.0/d.head;if(u>=0)q+=((d.tail,d.head::c,u));q+=((d.tail,c,r))}};(t.maxBy(_.size) :+n).sorted.map(i=>s"1/$i").mkString("+")}

```

Ungolfed version. Try it online!

```
import scala.collection.mutable.Queue

object Main {
  def f(n: Int): String = {
    var q: Queue[(List[Int], List[Int], Double)] = Queue((List.range(2, n), List(), 1 - (1.0/n)))
    var t: List[List[Int]] = List()
    while (q.nonEmpty) {
      val (d, c, r) = q.dequeue()
      if (d.isEmpty) {
        // if d is empty, continue with the next iteration
      } else if (BigDecimal(r).setScale(5, BigDecimal.RoundingMode.HALF_UP).toDouble == 0) {
        t = c :: t
      } else {
        val u = r - (1.0/d.head)
        if (u >= 0) {
          q += ((d.tail, d.head :: c, u))
        }
        q += ((d.tail, c, r))
      }
    }
    val maxList = t.maxBy(_.length) :+ n
    maxList.sorted.map(i => s"1/$i").mkString("+")
  }

  def main(args: Array[String]): Unit = {
    println(f(6))
    println(f(15))
    println(f(20))
  }
}

```

---
Tags: code-golf, math, sequence, rational-numbers
---


title: Strict partitions of a positive integer

text:
# Question
Title: Strict partitions of a positive integer
OEIS A000009 counts the number of *strict partitions* of the integers. A *strict partition* of a nonnegative integer `n` is a set of positive integers (so no repetition is allowed, and order does not matter) that sum to `n`.

For example, 5 has three strict partitions: `5`, `4,1`, and `3,2`.

10 has ten partitions:

```
10
9,1
8,2
7,3
6,4
7,2,1
6,3,1
5,4,1
5,3,2
4,3,2,1

```

## Challenge

Given a nonnegative integer `n`\<1000, output the number of strict partitions it has.

### Test cases:

```
0 -> 1

42 -> 1426

```

Here is a list of the strict partition numbers from 0 to 55, from OEIS:

```
[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718,6378]

```

This is , so the shortest solution in bytes wins.

# Answer
# Pyth, 7 bytes

```
l{I#./Q

```

Try it online. Test suite.

* Take the input (`Q`).
* Find its partitions (`./`).
* Filter it (`#`) on uniquify (`{`) not changing (`I`) the partition. This removes partitions with duplicates.
* Find the result's length (`l`).
> 4 votes

# Answer
## Python 2, 49 bytes

```
f=lambda n,k=1:n/k and f(n-k,k+1)+f(n,k+1)or n==0

```

The recursion branches at every potential summand `k` from `1` to `n` to decide whether it should be included. Each included summand is subtracted from the desired sum `n`, and at the end, if `n=0` remains, that path is counted.
> 4 votes

# Answer
# Mathematica, 11 bytes

```
PartitionsQ

```

---

**Test case**

```
PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)

```
> 4 votes

# Answer
## Haskell, 39 bytes

```
f n=sum[1|x<-mapM(:[0])[1..n],sum x==n]

```

The function `(:[0])` converts a number `k` to the list `[k,0]`. So,

```
mapM(:[0])[1..n]

```

computes the Cartesian product of `[1,0],[2,0],...,[n,0]`, which gives all subsets of `[1..n]` with 0's standing for omitted elements. The strict partitions of `n` correspond to such lists with sum `n`. Such elements are counted by a list comprehension, which is shorter than `length.filter`.
> 3 votes

# Answer
# Python, 68 bytes

```
p=lambda n,d=0:sum(p(n-k,n-2*k+1)for k in range(1,n-d+1))if n else 1

```

Just call the anonymous function passing the nonnegative integer `n` as argument... and wait the end of the universe.
> 2 votes

# Answer
## ES6, 64 bytes

```
f=(n,k=0)=>[...Array(n)].reduce((t,_,i)=>n-i>i&i>k?t+f(n-i,i):t,1)

```

Works by recursive trial subtraction. `k` is the number that was last subtracted, and the next number to be subtracted must be larger (but not so large that an even larger number cannot be subtracted). 1 is added because you can always subtract `n` itself. (Also since this is recursive I have to take care that all of my variables are local.)
> 2 votes

# Answer
# 05AB1E, 5 bytes

```
LæOQO

```

Try it online!

Note: this is extremely slow and will timeout for inputs greater than about 20.

Explanation:

```
L         # range 1..input
 æ        # list of subsets
  O       # sum each subset
   Q      # equal? (1 for each sum that equals the input, 0 otherwise)
    O     # sum the booleans

```
> 2 votes

# Answer
## Haskell, 58 bytes

```
import Data.List
h x=sum[1|i<-subsequences[1..x],sum i==x]

```

Usage example: `map h [0..10]` -\> `[1,1,1,2,2,3,4,5,6,8,10]`.

It's a simple brute-force approach. Check the sums of all subsequences of `1..x`. This works for `x == 0`, too, because all subsequences of `[1..0]` are `[[]]` and the sum of `[]` is `0`.
> 1 votes

# Answer
## Haskell, 43 bytes

```
0%0=1
_%0=0
n%k=n%(k-1)+(n-k)%(k-1)
f n=n%n

```

The binary function `n%k` counts the number of strict partitions of `n` into parts with a maximum part `k`, so the desired function is `f n=n%n`. Each value `k` can be included, which decreases `n` by `k`, or excluded, and either way the new maximum `k` is one lower, giving the recursion `n%k=n%(k-1)+(n-k)%(k-1)`.
> 1 votes

# Answer
# Vyxal `l`, 24 bitsv2, 3 bytes

```
Ṅ'Þu

```

Try it Online!

Vyxal forever
> 1 votes

# Answer
# Julia, 53 bytes

```
n->endof(collect(filter(p->p==∪(p),partitions(n))))

```

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

We get the integer partitions using `partitions`, `filter` to only those with distinct summands, `collect` into an array, and find the last index (i.e. the length) using `endof`.
> 0 votes

# Answer
# 05AB1E, 8 bytes

```
ÅœʒDÙQ}g

```

Try it online or verify all test cases.

**Explanation:**

```
Åœ          # Get all integer partitions of the (implicit) input
            #  i.e. 5 → [[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]
  ʒ   }     # Filter by:
   D        #  Duplicate the current partition
    Ù       #  Uniquify (removing any duplicated values from) this copied partition
            #   i.e. [1,1,1,1,1] → [1]
            #   i.e. [1,4] → [1,4]
     Q      #  Check if it's still the same
            #   i.e. [1,1,1,1,1] and [1] → 0 (falsey)
            #   i.e. [1,4] and [1,4] → 1 (truthy)
       g    # Then take the length of the filtered list (and implicitly output it)
            #  i.e. [[1,4],[2,5],[5]] → 3

```
> 0 votes

---
Tags: code-golf, math, sequence, integer-partitions
---


title: Find all Belphegor primes

text:
# Question
Title: Find all Belphegor primes
A Belphegor number is a number of the form \\$(10^{n+3}+666)\*10^{n+1}+1\\$ (`1{n zeroes}666{n zeroes}1`) where \\$n\\$ is an non-negative integer. A Belphegor prime is a Belphegor number that is also prime.

The \\$n\\$ values of the first few Belphegor primes are `0`, `13`, `42`, `506` (A232448)

# Task

Write a program that either:

* takes no input and outputs all Belphegor primes.
* takes a input \\$k\\$ and outputs the first \\$k\\$ Belphegor primes.

A reference python implementation can be found here.

# Rules

* You may output the \\$n\\$ value for the Belphegor prime instead of the prime itself
* You may use probabilistic primality tests as long as there is no known counter case.

# Scoring

This is so shortest bytes wins.

---

*Inspired by The Most Evil Number - Numberphile*

# Answer
> 5 votes
# 05AB1E, ~~14~~ ~~10~~ 9 bytes

```
∞°66+€ûʒp

```

Outputs the infinite sequence.
Extremely slow due to the prime-check on large numbers, so times out before it even reaches the `n=13` Belphegor prime on TIO..

Try it online or verify the numbers without the prime-check filter.

**Explanation:**

```
∞          # Push an infinite positive list: [1,2,3,4,5,...]
 °         # Take 10 to the power each: [10,100,1000,10000,100000,...]
  66+      # Add 66 to each: [76,166,1066,10066,100066,...]
     €û    # Palindromize each: [767,16661,1066601,100666001,10006660001,...]
       ʒ   # Filter the list by:
        p  #  Check whether it's a prime number
           #  (minor note: 767 is NOT a prime)
           # (after which the resulting list is output implicitly)

```

# Answer
> 4 votes
# Wolfram Language (Mathematica), 51 bytes

outputs the n value
"...program that does not stop and will eventually output all..."

```
PrimeQ[10^c*666+1+100^++c]~If~Print[c-2]~Do~{c,∞}

```

Try it online!

thanks to @DanTheMan for saving 4 bytes
and also to @mypronoun -7 bytes

# Answer
> 3 votes
# Ruby -rprime, 45 bytes

```
Prime.map{|p|p p if"#{p}"=~/^1(0*)666(\1)1$/}

```

Try it online!

Stutters, then checks all primes against a Belphegor prime regex. Very slow.

(Edit: Kudos to @Abigail, whose earlier Perl answer used a similar regex. I didn't notice it until after I posted my answer.)

# Answer
> 3 votes
# Pyth, 17 bytes

```
.fP_sj666_B`^TZQ0

```

Try it online!

Takes `k` as input and outputs the `n` corresponding to the first `k` Belphegor primes.

Explanation:

```
.fP_sj666_B`^TZQ0
.f             Q0    Find the first k values of Z where the following is true,
                     starting at 0 and counting upwards.
            ^TZ      Raise 10 to the power of Z
           `         Convert to a string
         _B          Pair with reversal
     j666            Join with 666 in the middle
    s                Convert to number
  P_                 Check for primality.

```

# Answer
> 2 votes
# Jelly, 19 bytes

```
+Ø½Ṭ6×1;ŒḄḌṄẒ¡×0µ1#

```

A full program which prints the Belphegor primes.

**Try it online!**

### How?

```
+Ø½Ṭ6×1;ŒḄḌṄẒ¡×0µ1# - Main Link: no arguments (implicit input = 0)
                µ1# - count up, from n = 0, finding the first n for which
                      this yields a truthy value:
 Ø½                 -   [1,2]
+                   -   add to n -> [n+1, n+2]
   Ṭ                -   un-truth -> [0]*n+[1,1]  (e.g. n = 3: [0,0,0,1,1])
    6×              -   multiply by six -> [0]*n+[6,6]
      1;            -   prefix with a one -> [1]+[0]*n+[6,6]
        ŒḄ          -   bounce -> [1]+[0]*n+[6,6,6]+[0*n]+[1]
          Ḍ         -   from base 10 -> 100...0066600...001
             ¡      -   repeat...
            Ẓ       -   ...number of times?: is prime?
           Ṅ        -   ...action?: print it and a newline character
              ×0    -   multiply the result by 0 (forcing an infinite loop)

```

# Answer
> 2 votes
# perl -M5.010 -Mbigint -Mexperimental=signatures, 62 70 bytes

```
sub p($m=3){$m>=$_||($_%$m&&p($m+2))}$_=16661;{p&&say;s/6+/0$&0/;redo}

```

Try it online!

@ikegami pointed out the original solution doesn't work, because `..` doesn't work well with bigints. So we replaced it with recursive function which checks whether a number is a prime (by checking whether it isn't evenly divisible by any odd digit less than the tested number (excecpt 1)). We also no longer iterating over all numbers, instead, we're just checking all the Belphegor numbers; we can easily make the next one from the previous by replacing `666` by `06660`.

It's still slow, because of the rather dumb primeness checking. Running it on TIO doesn't actually produce any output (it seems to run at most one minute). Running it from the command line quickly produces 16661, but I couldn't bother waiting for it to reach 1000000000000066600000000000001, the next Belphegor prime. It is likely to die from memory exhaustion when trying to determine one of the Belphegor numbers is prime, before finding 1000000000000066600000000000001 anyway.

# Answer
> 2 votes
# Python 3, 80 bytes

```
b=2
while 1:n=100**b+10**~-b*666+1;all(n%m for m in range(2,n))and print(n);b+=1

```

Try it online!

# Answer
> 1 votes
# Pyth, 22 bytes

```
.V0IP_h*+^T+3b666^Thbb

```

Try it online!

Implements the formula provided in the question. Prints the *n* values rather than the primes themselves.

Since this version (not surprisingly) times out on TIO, here is a version that prints all *n* values lower than the input: Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 71 bytes

A full program that prints Belphegor primes forever ... and takes forever to print them.

```
for(k=10n;;)for(d=n=666n*k+(k*=10n)*k+1n;n%--d||d<2n&&console.log(n););

```

Try it online!

### Commented

```
for(k = 10n;;)            // outer loop: start with k = 10 and loop forever
  for(                    //   inner loop:
    d = n =               //     start with d = n =
      666n * k +          //       666 * k +
      (k *= 10n) * k +    //       (10 * k)² +
      1n;                 //       1
                          //     and update k to 10 * k
      n % --d ||          //     decrement d until it divides n
        d < 2n &&         //     if d is less than 2:
          console.log(n); //       n is prime --> print it
  );                      //

```

---

### JavaScript (Node.js), 176 bytes (non-competing)

A *much* faster version that uses a single iteration of the Miller-Rabin primality test.

```
for(k=10n;;)(n=666n*k+(k*=10n)*k+1n,~-(x=(g=(d,r,a)=>d?g(d/2n,d&1n?r*a%n:r,a*a%n):r)(d=n/(~-n&1n-n),1n,2n))&&~x+n?(g=d=>~d+n?~-(x=x*x%n)?~x+n&&g(d+d):1:1)(d):0)||console.log(n)

```

Try it online!

I guess it doesn't comply with the challenge rules since the test is likely to produce false-positives. It does however find the same 5 first terms as other answers.

# Answer
> 1 votes
# Vyxal, 108 bitsv2, 13.5 bytes

```
Þ:'3+↵666+n›↵*›æ

```

Try it Online!

Using the `T` flag sets the interpreter to time out after 1 minute :P

# Answer
> 0 votes
# Python, ~~220~~ 164 bytes

```
def a(k,s=set()):
 for i in range(k):
  p=1;n=(10**(i+3)+666)*10**-~i+1
  for d in range(1,int(n**.5//1/2)):
   p*=n%-~(d*2)>0
   if~-p:break
  s.add(p*n)
 return s

```

Simple prime search by checking modulus below the square root; fastened by skipping every even divisor.

Likely there's room for improvement, as it becomes incredibly slow for k \> 10.

---

Edit: thanks to @JonathanAllan and @mathjunkie for ideas and sources. This update has heavy use of tweaks and bit-operations.

---
Tags: code-golf, number, sequence, number-theory, primes
---


title: Decrypt an Autokey Cipher

text:
# Question
Title: Decrypt an Autokey Cipher
The autokey cipher is closely related to the Vigenère cipher (both were invented by Blaise de Vigenère). Decryption involves the encrypted message and the key. For simplicity, let us assume all characters in the message and key are lowercase letters (no spaces, numbers or symbols etc.).

## How to decrypt the cipher

1. Convert all letters in the message and key into their 0-indexed counterparts. For example, 'A' is converted to 0, while 'Z' is converted to 25.
2. Subtract the first letter of the key from the first letter of the message, and wrap the result to be within 0 to 25 inclusive. For example, `2 - 6 = 22`.
3. Append this result to both the plaintext message and the key.
4. Repeat steps 2 and 3 for each letter in the message. Notice that after the initial key runs out, the key becomes the plaintext.
5. Convert the plaintext message back into a string of capital letters.

## Challenge

Write a program or function that, when given a message encrypted using an autokey cipher and its key, outputs the decrypted plaintext message.

* The message and key both contain only letters.
* You may assume that the message and key both contain at least 1 letter, but you *cannot assume* that the message is longer than the key.
* You may choose to have only lowercase or only capital letters.
* You may choose to instead take the input and output strings as lists of integers from 0 to 26 inclusive, however a program that processes letters is preferred.
    + For example, `hyezvazczz, auto ==> helloworld` would instead be `[7, 24, 4, 25, 21, 0, 25, 2, 25, 25], [0, 20, 19, 14] ==> [7, 4, 11, 11, 14, 22, 14, 17, 11, 3]`
    + You may also mix between string input/output and list input/output (e.g. input as two lists, output as string)

## Test Cases

```
(format: message, key ==> plaintext)

hyezvazczz, auto ==> helloworld
amrkegkaikmoqsuwyacegikmoq, alphabet ==> abcdefghijklmnopqrstuvwxyz
lavxxwgwgusgfaugth, amet ==> loremipsumdolorsit
nlfpe, verylongkey ==> short

```

# Answer
> 7 votes
# Haskell, ~~39~~ 35 bytes

```
m#k=(`mod`26)<$>zipWith(-)m(k++m#k)

```

Attempt This Online!

Takes and returns lists of ints. The test suite adds a couple functions to convert to and from strings for convenience.

### Explanation

The core thing we're doing here is zipping two lists on subtraction, followed by mod 26:

```
m#k=(`mod`26)<$>zipWith(-)m k
m#k=                           -- Operator # takes m(essage) and k(ey):
                zipWith(-)m k  -- Subtract elementwise, clipping to shorter length
    (`mod`26)<$>               -- Mod 26 each element

```

But we also need to recycle the plaintext as part of the key. Haskell's lazy evaluation makes this task straightforward. Instead of using `k` as the key directly, we use

```
k++m#k
k       -- The original key
 ++     -- concatenated with
   m#k  -- the result of the decryption

```

# Answer
> 6 votes
# x86-64 machine code, ~~27~~ 17 bytes

**EDIT**: -6 bytes thanks to @Command Master noting the "upwards" modulo branch can be deleted.

**EDIT**: -4 bytes thanks to @Neil pointing out `sub al, [rdx]`.

```
ac 2a 02 79 02 04 1a 48 ff c2 aa 48 39 ce 75 f0
c3

```

Input is provided via the `RDI`, `RSI`, `RDX` and `RCX` registers:

* `RSI` points to the input array
* `RCX` points to the end of the input array
* `RDX` points to the key array
* `RDI` points to the end of the key array

Output is written to `RDI`; there must be enough space after the end of the key array to store the output.

Input and output are in integer array form; one byte per number.

The register allocation matches the following C function prototype using the Linux x86-64 ABI:

```
extern void decrypt(char* output, const char* input, const char* key, const char* inputEnd);

```

**Disassembly** (Intel Syntax):

```
                 decrypt:
   0:   ac            lodsb         ; read input byte
   1:   2a 02         sub al, [rdx] ; subtract key byte
                 ; manual modulo operation:
   3:   79 02         jns .no_mod   ; if non-negative, don't adjust
                                    ; value range is [-25; 25], so this is fine
   5:   04 1a         add al,26
                 .no_mod:
   7:   48 ff c2      inc rdx
   a:   aa            stosb         ; write output
   b:   48 39 ce      cmp rsi,rcx
   e:   75 f0         jne decrypt
  10:   c3            ret

```

A test suite is available here.

# Answer
> 5 votes
# 05AB1E, 11 bytes

```
ˆε¯˜Nè-₂%Dˆ

```

Try it online!

## Explanation

This might be the first 05AB1E program I ever wrote which properly utilizes the global array. It saves the key in the global array, and each time appends something to it.

```
ˆε¯˜Nè-₂%Dˆ
ˆ            # Add the key to the global array
ε            # For each element in the ciphertext:
 ¯           # Push the global array
 ˜           # Flatten it, to account for the first element being a list
 N           # Push the iteration index
 è           # And index it to the global array
 -           # subtract that from the current element
 ₂%          # mod 26
 D           # create a duplicate
 ˆ           # and add it to the global array (the other one is left for the map)

```

# Answer
> 3 votes
# Vyxal, 84 bitsv2, 10.5 bytes

```
£⟑¥ḣ£-₄%:&J

```

Try it Online!

Or, try a test suite

Takes key then ciphertext. Uses lists of numbers for input and output, although the test case suite uses strings for convenience.

## Explained

```
£⟑¥ḣ£-₄%:&J
£            # Put the key in the register
 ⟑           # For each number in the ciphertext:
  ¥ḣ -       #   Subtract the head of the key from the ciphertext number
   ḣ£        #    and behead the key
      ₄%     #    Modulo the result by 25
        :&J  #    and append it to the key, leaving a copy on the stack

```

Created with the help of Luminespire.

# Answer
> 3 votes
# Charcoal, 14 bytes

```
⭆θ§β↨⊞Ｏη⁻ι§ηκ⁰

```

Try it online! Link is to verbose version of code. Takes input as two integer arrays and outputs a string. Explanation:

```
 θ              Input message
⭆               Map over values and join
   β            Lowercase letters
  §             Cyclically indexed by
         ι      Current value
        ⁻       Minus
           η    Input key
          §     Indexed by
            κ   Current index
     ⊞Ｏη        Push to input key
    ↨        ⁰  Last integer (i.e. the one just pushed)
⭆               Implicitly print

```

16 bytes to output as an array:

```
Ｉ﹪Ｅθ↨⊞Ｏη⁻ι§ηκ⁰Ｌβ

```

Try it online! Link is to verbose version of code. Explanation: As above, but the `§β` is removed,  is replaced with  to generate an array rather than a string, the `%Ｌβ` reduces modulo `26` (a literal `26` would require a separator from the literal `0`), and  casts to string for implicit print.

16 bytes to input the message as a string and the key as an array and output a string:

```
⭆θ§β↨⊞Ｏη⁻⌕βι§ηκ⁰

```

Try it online! Link is to verbose version of code. Explanation: The `⌕β` converts the message from letters to integers.

23 bytes to input the key as a string:

```
⭆θ§⊞Ｏυ§β⁻⌕βι⌕β§⁺⪪η¹υκ±¹

```

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

```
 θ                      Input message
⭆                       Map over characters and join
       β                Lowercase letters
      §                 Cyclically indexed by
           ι            Current message letter
         ⌕β             Convert to integer
        ⁻               Minus
                 η      Input key
                ⪪ ¹     Split into characters
               ⁺        Concatenated with
                   υ    Predefined empty list
              §         Indexed by
                    κ   Current message index
            ⌕β          Convert to integer
   ⊞Ｏυ                  Push to predefined empty list
  §                  ±¹ Last value i.e. character just pushed
                        Implicitly print

```

I tried several interesting alternative algorithms and the next best one was 24 bytes:

```
≔Ｅη⟦⌕βι⟧η⭆θ§β↨⊞Ｏ§ηκ⌕βι±¹

```

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

```
≔Ｅη⟦⌕βι⟧η

```

Convert the key from a string to a list of lists of integers e.g. `[[0], [20], [19], [14]]`.

```
⭆θ§β↨⊞Ｏ§ηκ⌕βι±¹

```

Convert each letter from the message to an integer, push it to the cyclically indexed key list, convert that from base `-1`, and convert back from an integer to a letter.

# Answer
> 3 votes
# , ~~58~~ 51 bytes

```
\(m,k){for(i in seq(m))k=c(k,m[i]<-(m-k)[i]%%26);m}

```

Attempt This Online!

---

# , 58 bytes

```
f=\(m,k)if(sum(m|1))c(l<-(m-k)[1]%%26,f(m[-1],c(k[-1],l)))

```

Attempt This Online!

Original recursive approach.

# Answer
> 3 votes
# Python, 55 bytes

```
lambda m,k:[k.append(v:=c-K)or v%26for c,K in zip(m,k)]

```

Uses the fact that list iterator (and so `zip` too) does not copy, it holds a "reference", and `zip`'ping a growing array works as expected here. Saves 3 bytes by moving `%26` to output part — key bytes do not have to belong to \\$\[0;\\,25\]\\$, modulus can be applied later. Accepts and outputs numeric lists.

Test cases taken from @SuperStormer's answer.

Attempt This Online!

# Answer
> 2 votes
# JavaScript (ES6), 47 bytes

Expects `(msg)(key)` as two arrays of integers in \\$\[0\dots25\]\\$. Returns an array in the same format.

```
m=>k=>m.map((c,i)=>k.push(v=(c-k[i]+26)%26)&&v)

```

Try it online!

# Answer
> 2 votes
# Python, 57 bytes

```
def f(m,k,i=0):
 for c in m:m[i]=v=(c-k[i])%26;k+=v,;i+=1

```

Attempt This Online!

Outputs by modifying arguments.

# Answer
> 1 votes
# Scala, ~~128~~ 124 bytes

Saved 4 bytes thanks to the comment of @SuperStormer

---

Golfed version. Try it online!

```
def d(c:Seq[Int],k:Seq[Int],p:Seq[Int]=Seq()):Seq[Int]=if(c.isEmpty)p else{val n=(c(0)-k(0)+26)%26;d(c.tail,k.tail:+n,p:+n)}

```

Ungolfed version. Try it online!

```
object Main {
  def decryptAutokey(cipherText: List[Int], key: List[Int]): List[Int] = {
    def decrypt(cipherText: List[Int], key: List[Int], plainText: List[Int]): List[Int] = cipherText match {
      case cipherHead :: cipherTail =>
        val newLetter = (cipherHead - key.head + 26) % 26
        decrypt(cipherTail, key.tail :+ newLetter, plainText :+ newLetter)

      case Nil => plainText
    }
    decrypt(cipherText, key, List())
  }

  def main(args: Array[String]): Unit = {
    val cipherText = List(7, 24, 4, 25, 21, 0, 25, 2, 25, 25)
    val key = List(0, 20, 19, 14)
    val plainText = decryptAutokey(cipherText, key)
    val plainTextChars = plainText.map(p => (p + 'a').toChar)
    println(plainTextChars.mkString(""))
  }
}

```

---
Tags: code-golf, string, cipher
---


title: Tips for radiation hardening

text:
# Question
Title: Tips for radiation hardening
The aim of this post is to gather all the tips that can often be applied to challenges.

Please only post answers which can apply to a large number of languages, and one tip per answer.

# Answer
# Create a path on the right hand side

In a 2D programming language, and with radiation that deletes or inserts bytes, a useful pattern is to create a path on the right hand side of the program, and get the pointer there quickly.

This is because deleting or adding a character will always change the length of a line and disturb this path. This lets you detect and adjust based on the disruption.

For example you can use this to avoid damaged lines, or intentionally execute them.

Here's an example where I've used this strategy: Construct a Geiger counter in Klein
> 2 votes

# Answer
# Trivial Tips

## Redundancy

This is a fairly obvious one, but redundancy can help.

For example, if you have a program in a string/function written multiple times, and then a small "core" program near the end that checks for the longest program, the program can likely survive a random hit, or even a few.
> 1 votes

---
Tags: tips, radiation-hardening
---


title: Complex permutation

text:
# Question
Title: Complex permutation
Given an array of integers as input(including negative integers), find all (can include duplicates) permutations that **do not** have the same number next to each other, then print them all out.
If no permutations were found, print Nothing or return an empty list or any consistent output indicating that none were found.
Note that the original array can be a permutation.

Test cases:

```
[0, 1, 1, 0] -> [1, 0, 1, 0], [0, 1, 0, 1]
[0, 1, 2, 0] -> [0, 1, 2, 0], [0, 2, 1, 0], [1, 0, 2, 0], [0, 1, 0, 2], [2, 0, 1, 0], [0, 2, 0, 1]
[0, 1, 0] -> [0, 1, 0]
[1, 1, 1] -> [] or Nothing
[0, 0, 1, 1] -> [0, 1, 0, 1], [1, 0, 1, 0]

```

This is , all usual golfing rules apply and the shortest answer (in bytes) wins!

Leaderboard:

```
var QUESTION_ID=244078;
var OVERRIDE_USER=8478;
var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;function answersUrl(d){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(d,e){return"https://api.stackexchange.com/2.2/answers/"+e.join(";")+"/comments?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){answers.push.apply(answers,d.items),answers_hash=[],answer_ids=[],d.items.forEach(function(e){e.comments=[];var f=+e.share_link.match(/\d+/);answer_ids.push(f),answers_hash[f]=e}),d.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){d.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),d.has_more?getComments():more_answers?getAnswers():process()}})}getAnswers();var SCORE_REG=function(){var d=String.raw`h\d`,e=String.raw`\-?\d+\.?\d*`,f=String.raw`[^\n<>]*`,g=String.raw`<s>${f}</s>|<strike>${f}</strike>|<del>${f}</del>`,h=String.raw`[^\n\d<>]*`,j=String.raw`<[^\n<>]+>`;return new RegExp(String.raw`<${d}>`+String.raw`\s*([^\n,]*[^\s,]),.*?`+String.raw`(${e})`+String.raw`(?=`+String.raw`${h}`+String.raw`(?:(?:${g}|${j})${h})*`+String.raw`</${d}>`+String.raw`)`)}(),OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(d){return d.owner.display_name}function process(){var d=[];answers.forEach(function(n){var o=n.body;n.comments.forEach(function(q){OVERRIDE_REG.test(q.body)&&(o="<h1>"+q.body.replace(OVERRIDE_REG,"")+"</h1>")});var p=o.match(SCORE_REG);p&&d.push({user:getAuthorName(n),size:+p[2],language:p[1],link:n.share_link})}),d.sort(function(n,o){var p=n.size,q=o.size;return p-q});var e={},f=1,g=null,h=1;d.forEach(function(n){n.size!=g&&(h=f),g=n.size,++f;var o=jQuery("#answer-template").html();o=o.replace("{{PLACE}}",h+".").replace("{{NAME}}",n.user).replace("{{LANGUAGE}}",n.language).replace("{{SIZE}}",n.size).replace("{{LINK}}",n.link),o=jQuery(o),jQuery("#answers").append(o);var p=n.language;p=jQuery("<i>"+n.language+"</i>").text().toLowerCase(),e[p]=e[p]||{lang:n.language,user:n.user,size:n.size,link:n.link,uniq:p}});var j=[];for(var k in e)e.hasOwnProperty(k)&&j.push(e[k]);j.sort(function(n,o){return n.uniq>o.uniq?1:n.uniq<o.uniq?-1:0});for(var l=0;l<j.length;++l){var m=jQuery("#language-template").html(),k=j[l];m=m.replace("{{LANGUAGE}}",k.lang).replace("{{NAME}}",k.user).replace("{{SIZE}}",k.size).replace("{{LINK}}",k.link),m=jQuery(m),jQuery("#languages").append(m)}}
```

```
body{text-align:left!important}#answer-list{padding:10px;float:left}#language-list{padding:10px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/primary.css?v=f52df912b654"> <div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table>
```

# Answer
> 3 votes
# Vyxal, 4 bytes

```
Ṗ'¯A

```

Try it Online!

Port of Jonathan Allan's Jelly answer.

-1 thanks to ovs.

# Answer
> 3 votes
# BQN, 35 bytesSBCS

```
{(∧´1«»≠⊢)¨⊸/⍷⊏˜⚇1⍋∘⍋⊸≡˜¨⊸/⥊↕⥊˜≠}

```

Run online!

# Answer
> 3 votes
# , 30 bytes

```
[:~.@(#~0=1#.2=/\"1])i.@!@#A.]

```

Try it online!

# Answer
> 3 votes
# Haskell, 69 bytes

```
import Data.List
f=(filter$and.(zipWith(/=)<*>tail)).nub.permutations

```

Try it online!

# Answer
> 3 votes
# Factor \+ `grouping.extras math.combinatorics`, 59 bytes

```
[ [ [ = ] 2clump-map vnone? ] filter-permutations members ]

```

Try it online!

* `[ ... ] filter-permutations` Select the permutations of the input for which `[ ... ]` returns true.
* `[ = ] 2clump-map` Map `=` to every two elements of a sequence with overlapping. e.g. `{ 1 0 1 1 2 } [ = ] 2clump-map` -\> `{ f f t f }`
* `vnone?` Returns true only if every element of a sequence is `f`.
* `members` Get the unique elements of a sequence.

# Answer
> 3 votes
# PARI/GP, 73 bytes

```
f(x)=r=[];forperm(vecsort(x),p,prod(i=2,#p,p[i]-p[i-1])&&r=concat(r,p));r
```

Attempt This Online!

After a lot of head scratching and asking @alephalpha in chat, here it is.

# Answer
> 3 votes
# 05AB1E, 5 bytes

```
œʒ¥ĀP

```

Includes duplicated items.

Try it online or verify all test cases.

**Explanation:**

```
œ      # Get all permutations of the (implicit) input-list
 ʒ     # Filter it by:
  ¥    #  Get the deltas/forward-differences
   Ā   #  Check for each whether it's NOT 0
    P  #  Product: check if all of them are truthy
       # (after which the result is output implicitly)

```

`¥Ā` could alternatively be `üÊ` for the same byte-count:

```
  ü    #  For each overlapping pair:
   Ê   #   Check that they are not equal

```

# Answer
> 3 votes
# C++ (gcc), ~~310~~ ~~301~~ ~~283~~ 278 bytes

EDIT: -22 bytes thanks to `ceilingcat` and -1 byte from the label statement.

```
#include"bits/stdc++.h"
#define c std::cout<<
#define Q&a[0],&*end(a))
#define T;for(j=0;j<a.size()
int j,k;l(std::deque<int>a){auto p=[&]{c"["T;)c","+!j<<a[j++];c"]";};p();c"->";for(std::sort(Q;std::next_permutation(Q;){T-1;)if(a[j]==a[++j])goto e;c","+1/++k;p();e:;}k||c"[]";}

```

Try it online!

# Answer
> 2 votes
# Jelly, 6 bytes

```
Œ!IẠ$Ƈ

```

**Try it online!**

### How?

```
Œ!IẠ$Ƈ - Link: list of numbers, A
Œ!     - all permutations of A
     Ƈ - filter keep those for which:
    $  -   last two links as a monad:
  I    -     forward differences
   Ạ   -     all non-zero?

```

# Answer
> 2 votes
# Python 3, 88 bytes

*Thanks to user `loopy walt` for `-7 bytes` and user pxeger for `-1 byte`.*
Returns a set of non-duplicate tuples. For the `nothing` case an empty `set()` is returned.

```
lambda l:{p for p in permutations(l)if p[:len([*groupby(p)])]==p}
from itertools import*

```

Attempt This Online!

# Python 3.10, 95 bytes

*Thanks to user `LeopardShark` for `-1 byte`.*

```
lambda l:{p for p in permutations(l)if all(i!=j for i,j in pairwise(p))}
from itertools import*

```

Attempt This Online!

# Answer
> 2 votes
# JavaScript (ES6), 90 bytes

Returns a set of strings.

```
f=(a,p=[],s=new Set)=>a.map((v,i)=>v==p[0]||f(a.filter(_=>i--),[v,...p],s))+a?s:s.add(p+a)

```

Try it online!

# Answer
> 2 votes
# Ruby, ~~55~~ 53 bytes

```
->l{[]|l.permutation.select{|r,*f|f.all?{|x|r!=r=x}}}

```

Try it online!

Thanks AZTECCO for -2 bytes

# Answer
> 2 votes
# Curry (PAKCS), 53 bytes

```
[]#s=s
(x++a:y)#s|s==[]||a/=head s=(x++y)#(a:s)
(#[])

```

Try it online!

Curry supports non-deterministic operations which can return different values for the same input. This is a non-deterministic function whose different return values are the all complex permutations (including duplicates).

# Answer
> 2 votes
# Brachylog, 10 bytes

```
p.{s₂=}ᶜ0∧

```

A generator predicate that takes a list through its input parameter and produces permutations (including duplicates) through its output parameter. Try it online!

### Explanation

```
p.{s₂=}ᶜ0∧
p           Get a permutation of the input list
 .          This is the output
  {   }ᶜ    Count the number of ways to:
   s₂        Get a length-2 sublist
     =       whose elements are equal
        0   Assert that the result is 0
         ∧  Don't try to unify 0 with the output

```

# Answer
> 0 votes
# Scala, 162 bytes

Port of @G B's Ruby answer in Scala.

---

Golfed version. Try it online!

```
def u(l:List[Int])=l.permutations.filter(i).toList
def i(l:List[Int]):Boolean=l match{case Nil=>true case _::Nil=>true case x::y::xs=>if(x==y)false else i(y::xs)}

```

Ungolfed version. Try it online!

```
object Main {
  def uniquePermutations(list: List[Int]): List[List[Int]] = {
    list.permutations.filter(isUniqueConsecutive).toList
  }

  def isUniqueConsecutive(list: List[Int]): Boolean = {
    list match {
      case Nil => true
      case _::Nil => true
      case x::y::xs => if (x == y) false else isUniqueConsecutive(y::xs)
    }
  }

  def main(args: Array[String]): Unit = {
    println(uniquePermutations(List(0, 1, 1, 0)))
    println(uniquePermutations(List(1, 1, 1)))
  }
}

```

# Answer
> 0 votes
# , 93 bytes

```
\(v,m=permute::allPerms(v))for(i in 1:nrow(m)){l=v[m[i,]];if(all(l!=lag(l),na.rm=T))print(l)}

```

Prints in console, including duplicates:

> v=c(0,-2,1,0) ; a(v)

> \[1\] 0 -2 0 1
> \[1\] 0 1 -2 0
> \[1\] 0 1 0 -2
> \[1\] -2 0 1 0
> \[1\] -2 0 1 0
> \[1\] 1 0 -2 0
> \[1\] 1 0 -2 0
> \[1\] 0 -2 0 1
> \[1\] 0 -2 1 0
> \[1\] 0 1 0 -2
> \[1\] 0 1 -2 0

---
Tags: code-golf, array, permutations
---


title: Write a set as a union of ranges

text:
# Question
Title: Write a set as a union of ranges
In this challenge, we define a *range* similarly to Python's `range` function: A list of positive integers with equal differences between them. For example, `[1, 2, 3]` is a range from 1 to 3 with a skip count of 1, because there is a difference of 1 between each item, and `[4, 7, 10, 13]` is a range from 4 to 13 with a skip count of 3.

Here, I'll represent ranges as a list of integers, but you can use any reasonable format that unambiguously represents a single range, e.g representing it as `[start, skip, end]` or something.

Your challenge is to, given a strictly increasing list of positive integers, represent it as a union of multiple ranges of integers with as few ranges as possible. For example, `[1, 2, 4, 7, 12]` can be represented as a union of `[1, 4, 7]` and `[2, 7, 12]`, and this is (an) optimal solution as it uses two ranges and there is no way to represent it as one range.

This is , shortest wins!

## Testcases

Note that these only show one possible solution. In almost all cases there will be multiple optimal solutions, and you can output any one or all of them.

```
[1, 5] -> [1, 5]
[1, 2, 3] -> [1, 2, 3]
[1, 2, 4, 7, 12] -> [1, 4, 7], [2, 7, 12]
[1, 2, 3, 11, 12, 13, 21, 22, 23] -> [1, 2, 3], [11, 12, 13], [21, 22, 23]
[8, 9, 13] -> [8, 9], [13]
[23, 24, 25, 27, 30, 33, 35, 37, 40, 44, 45] -> [24, 27, 30, 33], [23, 30, 37, 44], [25, 30, 35, 40, 45]
[1,2,3,4,5,6,7,9,10,11,12,13,14,15] -> [1,2,3,4,5,6,7], [9,10,11,12,13,14,15]
[1, 2, 4, 7, 12, 17] -> [1, 4, 7], [2, 7, 12, 17]

```

# Answer
# 05AB1E, ~~13~~ 12 bytes

-1 thanks to @KevinCruijssen

```
æʒ¥Ë}æé.Δ˜êQ

```

Try it online!

```
æ       # all subsets
ʒ       # keep those such that
 ¥       # their deltas
 Ë       # are all equal
}
æ       # look at sets of such ranges
é       # sorted by length
.Δ      # and return the first one such that
 ˜       # flattened
 ê       # and sort uniquified
 Q       # and is equal to the implicit input

```
> 10 votes

# Answer
# Haskell \+ hgl, 31 bytes

```
mBl<(sSt<iS^.sr<fo*^sSt(lq<δ))

```

This is really quite slow.

## Explanation

* `sSt(lq<δ)` get all sublists of the input that have constant deltas
* `sSt<iS^.sr<fo` get all sublists of the above that contain the input when unioned
* `mBl` get the minimum by length

## Reflection

There are a few things that could be improved here. I will note separately things that improve the golf score, and things that don't necessarily improve the golf score but help with speedy ways to complete this.

### Golf improvements

* Support for sets has been on my todo for a while, this answer really could have benefited from that. Here are some things I could have used here:
    + Some sort of union for lists
    + Some sort of subset for list (are all of this lists elements contained in this other list?)
* `lss` gets the longest sublist satisfying a predicate but there is no function to get the shortest sublist satisfying a predicate. That should exist.
* This is the second time I have used `lq<δ` in a challenge. It should have an abbreviation at this point.

### Performance improvements

* It would be nice to have a version of `sSt` restricted to non-empty lists. This wouldn't change the big O complexity or anything but it would halve the number of checks that need to be performed.
* As an extension of the above it would be nice to have a version of `sSt` which would only give the maximum elements, i.e. it would give only subsequences satisfying a predicate that are not subsequences of other subsequences also satisfying the predicate. In our case we don't need to care about the set `[2]` or `[2,3]` or `[3]` etc. if the set `[2,3,4]` is present, so eliminating those other ones would save a ton of time. It would be fastest if it never generated the bad subsequences, however either way would speed things up.
> 6 votes

# Answer
# JavaScript (Node.js), 127 bytes

```
f=(a,b=m=a,...p)=>m=p[m.length]?m:b+b?a.map(n=>f(a,a.filter(v=>v-i?b.includes(v):c.push(v)>(i+=n),n-=i=b[0],c=[]),...p,c))&&m:p

```

Try it online!

```
f=(
  a, // `a` is the input array
  b= // `b` is uncovered numbers
    m=a, // `m` is best solution we have ever found
         // initialize use `a` as length of `a` greater than best answer
  ...p // all ranges we have used, initialized as empty array
)=>m= // save best answer we found to `m`
  p[m.length]?m: // if currently used ranges is more than best answer
                 // give up attempt and return `m` directly
  b+b? // if there are numbers not covered yet
    a.map(n=> // for each number `n` in input
              // generate a range contains `b[0]` and `n` and step `n-b[0]`
      f(a,
        a.filter(v=> // for each number in input
          v-i?b.includes(v): // keep it in `b` as is if it not belongs to new range
          c.push(v)> // otherwise, add it to new range
            (i+=n), // calculate next expected number
                    // the next expected number >= length of `c`
                    //   so it is false, and filter this number out from `b`
          n-=i=b[0], // `i` is next number expected in the new range
                     // `n` is step of the new range
          c=[] // `c` is the new range
        ),...p,c)
      )&&m: // returns the best answer got so far
    p // found a better solution, assign it to m

```
> 3 votes

# Answer
# JavaScript (ES13), 148 bytes

Some kind of a compromise between golfiness and speed.

Output ranges are in reverse order (+5 bytes if this is not acceptable).

```
f=(a,n=0)=>(g=a=>a.reduce((b,x)=>b.flatMap(y=>(x.at?y[n]:2*y[0]-y[1]-x)?[y]:[y,[x,...y]]),[[]]))(g(a)).find(b=>!a[new Set(b.flat()).size])||f(a,n+1)

```

Attempt This Online!

## Commented

### Helper function `g`

This function computes the powerset of its input, applying the following constraints:

* If the input contains integers, we make sure that the output sets are valid 'ranges' (as per the Python definition).
* If the input contains arrays, we make sure that the output sets contain at most `n+1` entries (where `n` is defined in the scope of the main function).

```
g = a =>           // a[] = input array
a.reduce((b, x) => // for each array x[] in a[],
                   // using b[] as the accumulator
  b.flatMap(y =>   //   for each array y[] in b[]:
    (              //
      x.at ?       //     if x is an array:
        y[n]       //       test whether y[n] is defined
      :            //     else:
        2 * y[0] - //       test whether y[0] - x is equal
        y[1] -     //       to y[1] - y[0]
        x          //
    ) ?            //     if the above test is truthy:
      [y]          //       just pass y[]
    :              //     else:
      [            //
        y,         //       pass y[]
        [x, ...y]  //       create a new entry with x
      ]            //       inserted at the beginning of y[]
  ),               //   end of flatMap()
  [[]]             //   start with b[] = [ [] ]
)                  // end of reduce()

```

### Main function `f`

This function recursively attempts to find a solution using a single range, then two ranges, and so on. The counter `n` holds the maximum number of ranges, minus 1.

```
f = (              // f is a recursive function taking:
  a,               //   a[] = input array
  n = 0            //   n = counter
) =>               //
g(                 // get the powerset ...
  g(a)             //   ... of the powerset of a[],
)                  // using the constraints described above
.find(b =>         // look for an array b[] in there:
  !a[              //   such that the total number of distinct
    new Set(       //   items in b[] is equal to the length of
      b.flat()     //   the input array
    ).size         //   (i.e. a[number_of_items] is undefined)
  ]                //
)                  // end of find()
|| f(a, n + 1)     // if not found, try again with n + 1

```
> 2 votes

# Answer
# Python3, 306 bytes

```
def f(s):
 q,S=[[[s[0]]]],[]
 while q:
  b=q.pop(0)
  if S and len(b)>=len(S):continue
  U={i for j in b for i in j}
  if not{*s}-U:S=b;continue
  if len(B:=b[-1])<2:
   for i in s:
    if i>B[-1]:q+=[b[:-1]+[B+[i]]]
  elif(y:=2*B[-1]-B[-2])in s:q=[b[:-1]+[B+[y]]]+q
  else:q+=[b+[[min({*s}-U)]]]
 return S

```

Try it online!

A little long, but runs in 0.026 seconds on all test cases.
> 2 votes

# Answer
# Ruby, ~~126 ...~~ 101 bytes

```
->l{t=a=[];t,*a=a|l.product(l,l).map{|a,b,c|t+[[*a.step(b,c>a ?c-a:1)]]}while t.flatten.sort|[]!=l;t}

```

Try it online!

### Let me explain:

First, initialize 2 empty lists, one as a list of possible solutions, and one as an iterator on the list.

```
->l{t=a=[];

```

On every iteration: t is the first element of the list. We append all possible solutions including the previous value of `t` and another range to the list. This way, we check all solutions breadth-first.

```
t,*a=a|l.product(l,l).map{|a,b,c|t+

```

The ranges are calculated by getting 3 values `a, b, c` from the initial list, then going from `a` to `b` using `c-a` as increment. We need to be careful in case `c==a` (the step is 0 which is an error)

```
[[*a.step(b,c>a ?c-a:1)]]}

```

Check in the while-loop if `t` is a solution (must be the same as the input list if flattened and sorted).

```
while t.flatten.sort|[]!=l;t}

```
> 1 votes

# Answer
# Python 3.8 (pre-release), ~~217~~ 216 bytes

```
def f(s):
 q,*S=[[[s[0]]]],
 while q:b,*q=q;R={*s}-{*sum(b,[])};*T,B=b;*_,Z=B;0<len(S)<=len(b)or(R and(q:=(len(B)<2and[T+[B+[i]]for i in s if i>Z]or[[b+[[min(R)]],T+[B+[y:=2*Z-B[-2]]]][y in s]])+q)or(S:=b))
 return S

```

Try it online!

Severely golfed answer by Ajax1234.

Monads are awesome - `{*sum(b,[])}` is significantly shorter compared to plain comprehension (`{i for j in b for i in j}`).
> 1 votes

# Answer
# Charcoal, 62 bytes

```
⊞υ⟦θ⟧Ｆυ¿¬ⅉ«≔⊟ικＦΦ⁻θ⌊κ›λ⁰«≔⟦⌊κ⟧ζＷ№θ⁺⌈ζλ⊞ζ⁺⌈ζλ≔⁺ι⟦ζ⁻κζ⟧ζ¿⌊ζ⊞υζＩζ

```

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

```
⊞υ⟦θ⟧Ｆυ

```

Start a breadth-first search with no ranges in the union and the input list as the remaining elements.

```
¿¬ⅉ«

```

Stop once a solution is found (which will necessarily have a minimum number of ranges).

```
≔⊟ικ

```

Get the remaining numbers.

```
ＦΦ⁻θ⌊κ›λ⁰«

```

Loop over the potential step sizes.

```
≔⟦⌊κ⟧ζＷ№θ⁺⌈ζλ⊞ζ⁺⌈ζλ

```

Calculate the largest set that contains the minimum remaining element with this step size.

```
≔⁺ι⟦ζ⁻κζ⟧ζ

```

Calculate the elements remaining after this set is excluded and create a new union with this set and the remaining elements.

```
¿⌊ζ⊞υζＩζ

```

If there are elements remaining then add this union so far to the list of unions to be processed otherwise print this union.
> 0 votes

---
Tags: code-golf, math, set-partitions
---


title: Dense Number Sequence

text:
# Question
Title: Dense Number Sequence
OEIS: A167171

A *dense number* is a number that has exactly as many prime divisors as non-prime divisors (including 1 and itself as divisors). Equivalently, it is either a prime or a product of two distinct primes. The first 100 dense numbers are:

```
2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 67, 69, 71, 73, 74, 77, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 103, 106, 107, 109, 111, 113, 115, 118, 119, 122, 123, 127, 129, 131, 133, 134, 137, 139, 141, 142, 143, 145, 146, 149, 151, 155, 157, 158, 159, 161, 163, 166, 167, 173, 177, 178, 179, 181, 183, 185, 187, 191, 193, 194

```

Given a nonnegative integer `n`, output `dense(n)`. `n` may be 0-indexed or 1-indexed.

## Reference implementation (Sage)

```
import itertools

def dense_numbers():
    n = 1
    while True:
        prime_divisors = [x for x in divisors(n) if x.is_prime()]
        non_prime_divisors = [x for x in divisors(n) if not x.is_prime()]
        if len(prime_divisors) == len(non_prime_divisors):
            yield n
        n += 1

N = 20

print itertools.islice(dense_numbers(), N, N+1).next()

```

Try it online

# Answer
> 3 votes
# Jelly, 9 bytes

```
ÆE²Sḍ2µ#Ṫ

```

Reads from STDIN and uses 1-based indexing. Try it online!

### How it works

```
ÆE²Sḍ2µ#Ṫ  Main link. No arguments. Implicit argument: 0

      µ#   Read an integer n from STDIN and execute the chain to the left for
           k = 0, 1, 2, ... until n of them return a truthy value.
           Return the array of matches.
ÆE           Compute the exponents of k's prime factorization.
  ²          Square each exponent.
   S         Compute the sum of all squares.
    ḍ2       Test if 2 is divisible by the result (true iff  the sum is 1 or 2).
        Ṫ  Tail; extract the last (n-th) matching value of k.

```

# Answer
> 1 votes
## 05AB1E, ~~12~~ 11 bytes

1-indexed

```
µ             # while counter != input
 NÑ           # get divisors of current number
   p          # check if prime
    D         # duplicate
     O        # sum one copy
      s_O     # invert and sum the other copy
         Q½   # if equal increase counter

```

Try it online

# Answer
> 1 votes
# Brachylog, 17 bytes

```
:1yt.
1<.=$p#dl<3

```

Try it online!

### Predicate 0 (main predicate)

```
:1yt.
:1y     Find the first (input) solutions of predicate 1
   t    Last element
    .   Unify with output

```

### Predicate 1 (auxiliary predicate)

```
1<.=$p#dl<3
1<.            1 < output
  .=           assign a value to output
  . $p#d       output's prime factorization contains no duplicate
        l      and the length
         <3    is less than three

```

# Answer
> 1 votes
# Actually, 12 bytes

**All credits to Dennis for his algorithm.**

```
`w♂N;*2%Y`╓N

```

Try it online!

```
`w♂N;*2%Y`╓N

`        `     define a function
 w             prime factorization in exponent form:
               18 = (2^1)*(3^2) becomes [[2,1],[3,2]]
  ♂N           get the last element (exponent) of each sublist
    ;*         dot-product with self; equivalent to squaring
               each item and then taking the sum
      2%Y      test divisibility by 2
          ╓    first (input) solutions to the above function
           N   get the last element.

```

# Answer
> 1 votes
# Husk, 13 bytes

```
!fö`¦2ṁo□LgpN

```

Try it online!

## Explanation

```
!fö`¦2ṁo□LgpN
            N List of natural numbers
 fö           filtered by the following 4 functions:
          gp  prime factorization, grouped into equal runs
      ṁo□L    get length of each run, square and sum
   `¦2        is 2 divisible by the sum?
!             nth element in filtered list

```

# Answer
> 1 votes
# Vyxal `rG`, 56 bitsv2, 7 bytes

```
λ∆ǐ²∑2Ḋ;ȯ

```

Try it Online!

port of jelly

# Answer
> 0 votes
# R, 93 Bytes

```
dense=function(n){a=b=0;for(i in which(!n%%1:n))if(which(!i%%2:i)+1==i)a=a+1 else b=b+1;a==b}

```

It has a tendency to throw a warning. Its not really a problem. Allowing the warning saves me 5 bytes.

Ungolfed

```
dense=function(n){
     a=b=0                                #Initializing
     factors = which(!n%%1:n)             #Finds all factors
     for(i in factors)                    #Loops through factors
         prime = which(!i%%2:i)+1==i      #Tests if current factor is prime. If it is -- the first term in this vector will be TRUE. Otherwise, it will be false.
           if (prime) a=a+1 else b=b+1    #If first term is true, add 1 to a. Else add one to b.
      return(a==b)                        #Test equality of a and b.
}

```

# Answer
> 0 votes
# Python, 79 bytes

```
f=lambda n,k=2:n<1or-~f(n-(sum((k%i<1)+2*(k%i**2<1)for i in range(2,k))<3),k+1)

```

Uses 1-based indexing. Test it on Ideone.

# Answer
> 0 votes
# PHP, 118 Bytes

```
for($i=1;!$o=$s[$argn];$r[2]?:$t+=2*$$i=1,$t?:$s[]=$i)for($t=0,$r=[],$n=++$i;$n;$n--)$i%$n?:$t+=${$r[]=$n}?:-1;echo$o;

```

Try it online!

# Answer
> 0 votes
# Axiom, 102 bytes

```
f(n:PI):PI==(i:=1;repeat(i:=i+1;a:=divisors(i);2*#[x for x in a|prime?(x)]=#a=>(n=1=>break;n:=n-1));i)

```

ungolf and result

```
-- 1 base Indexed: return the n_th number i that has 2*#divisorsPrimeOf(i)=#divisors(i)
ff(n:PI):PI==
     i:=1
     repeat
        i:=i+1
        a:=divisors(i)
        2*#[x for x in a|prime?(x)]=#a=>(n=1=>break;n:=n-1)
     i

(3) -> [f(i)  for i in 1..23]
   (3)  [2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,31,33,34,35,37,38]
                                               Type: List PositiveInteger

```

---
Tags: code-golf, number, sequence, number-theory, primes
---