title: List Sophie Germain primes

text:
# Question
Title: List Sophie Germain primes
# The Question

A *Sophie Germain prime* is a prime \\$p\\$ such that \\$2p+1\\$ is prime as well. For example, 11 is a Sophie Germain prime because 23 is prime as well. Write the shortest program to calculate Sophie Germain primes in ascending order

# Rules

* The Sophie Germain primes must be generated by **your** program, not from an external source.
* Your program **must** calculate all Sophie Germain primes under \\$2^{32}-1\\$
* You must print each distinct Sophie Germain prime your program finds.
* The person with the lowest score wins

# Scoring

* 2 points per byte of your code
* -10 if you can show a prime generated by your program greater than \\$2^{32}-1\\$

# Answer
> 5 votes
# Pyth, 19 bytes * 2 - 10 = 28

Note that the online compiler/executor doesn't show output because it's an infinite loop.

```
K1#~K1I&!tPK!tPhyKK

```

Explained:

```
K1                      K=1
  #                     While true:
   ~K1                  K+=1
      I                 If
       &                logical AND
        !tPK            K is prime
            !tPhyK      2*K+1 is prime (y is double, h is +1)
                  K     Print K

```

# Answer
> 4 votes
# CJam

For 17 chars we get full enumeration up to 2^32:

```
G8#,{_mp*2*)mp},`

```

For 4 chars more, we get a range just large enough to include an SG prime greater than 2^32:

```
G8#K_*+,{_mp*2*)mp},`

```

since 4294967681 = 2^32 + 385 \< 2^32 + 400.

Of course, we could equally extend the range for free as

```
C9#,{_mp*2*)mp},`

```

# Answer
> 4 votes
# Husk, ~~16~~ ~~8~~ 7 * 2 - 10 = 4

*~~-8~~ 12 thanks to @Jo King*

```
fȯṗ→Dİp

```

Try it online!

A list of all natural numbers that are Sophie Germain primes. I hope it's valid, because it doesn't terminate when you try to show the entire list, but Husk lazily evaluates it, so you can just take the required amount.

```
fȯṗ→Dİp
f         Filter
     İp   the prime numbers
    D     that, when doubled
   →      and incremented by 1
 ȯṗ       are prime

```

Another way to do it, also 7 bytes:

```
fṗm÷2İp

```

# Answer
> 3 votes
# 05AB1E, 7 bytes, score = 4

*Thanks to @ovs for -1 byte!*

```
∞ʒx>‚pP

```

(Technically) Prints an infinite list of Sophie Germain primes! (Hence, score is subtracted by 10)

Try it online!

## How?

```
∞ʒ        # For each natural number 'p'...
  x>‚     # Pair p with 2p + 1 (The ‚ is not a comma, it is a weird sort of quotation)
     p    # Are they both prime?
      P   # Then multiply the boolean values! (And implicitly print if the product is 1)

```

# Answer
> 2 votes
# Pyth - 2 * 16 bytes - 10 = 22

Uses the customary method of prime checking in Pyth with the `!tP` and applies it both to the number and its safe-prime, with a little trick to check both at once. Goes up to `10^10`, so I'm going for the bonus.

```
f!+tPTtPhyTr2^TT

```

Explanation coming soon.

```
f          r2^TT     Filter from 2 till 10^10
 !                   Logical not to detect empty lists
  +                  List concatenation
   tP                All but the firs element of the prime factorization
    T                The filter element
   tP                All but the firs element of the prime factorization
    hyT              2n+1

```

Try under 1000 online.

# Answer
> 2 votes
# APL (Dyalog Extended), `10 - ⍨ 2 × 27` = 44

```
f←{⎕←⍵⍴⍨⌽∧\1⍭⍵,1+2×⍵⋄∇⍵+1}1+⊢

```

Try it online!

Made with some golfing help and general APL help from dzaima.

## Explanation

```
{⎕←⍵⍴⍨⌽∧\1⍭⍵,1+2×⍵⋄∇⍵+1}1+⊢
                        1+⊢ add 1 to the input (initially, 1)
             1+2×⍵          double and increment it
         1⍭⍵,               prepend the primality check(1 or 0)
       ∧\                   and scan with LCM
   ⍵⍴⍨⌽                     reverse & reshape using self
                            (if test is falsy, then this results in ⍬)
 ⎕←                         and display it with newline

```

# Answer
> 2 votes
# Vyxal, 6 bytes, score 2

```
Þp:d›↔

```

Try it Online!

```
     ↔ # Union of...
Þp     # Primes
  :d›  # Primes * 2 + 1

```

-10 score because it prints an infinite list.

# Answer
> 2 votes
# Nekomata, 4 bytes, score -2

```
Ƥ←½Q

```

Attempt This Online!

```
Ƥ←½Q
Ƥ          Non-deterministically choose a prime number
 ←         Decrement
  ½        Divide by 2
   Q       Check if result is a prime

```

By default, Nekomata prints all possible results.

# Answer
> 1 votes
# CJam, 34 (2 * 22 - 10)

```
C9#{ImpI2*)mp&{Ip}&}fI

```

Prints all Sophie Germain primes under `12 ** 9`, which includes `4294967681 > 2 ** 32`.

I estimate that this will take roughly 8 hours on my machine. I'll run it tonight.

# Answer
> 1 votes
# Python 3, ~~124~~ 123 bytes

```
i=3
q=[2]
while 1:
 p=1
 for x in range(2,round(i**.5)+1):p=min(p,i%x)
 if p:
  q+=[i];s=(i-1)/2
  if s in q:print(s)
 i+=2

```

How does it work?

```
i=3                                 # Start at 3
q=[2]                               # Create list with first prime (2), to be list of primes.
while 1:                            # Loop forever
 p=1                                # Set p to 1 (true)
 for x in range(2,round(i**0.5)+1): # Loop from 2 to the number's square root. x is the loop value
     p=min(p,i%x)                   # Set p to the min of itself and the modulo of
                                    # the number being tested and loop value (x).
                                    # If p is 0 at the end, a modulo was 0, so it isn't prime.
 if p:                              # Check if p is 0
  q+=[i]                            # Add the current number (we know is prime) to list of primes (q)
  s=(i-1)/2                         # Generate s, the number that you would double and add 1 to make a prime.

  if s in q:print(s)                # If (i-1)/2 is a prime (in the list), then that prime satifies
                                    # the condition 2p+1 is prime because i is 2p+1, and i is prime
 i+=2                               # Increment by 2 (no even numbers are prime, except 2)

```

Try it online here.

---

My computer says it is has generated 0.023283 % of all the Sophie Germain primes below 2^32.

When it's finished, I'll post it on pastebin if there are enough lines. You can use it to check you've got them all.

# Answer
> 1 votes
# Haskell, 2\*54-10 = 98 ~~132~~

```
i a=all((>0).rem a)[2..a-1]
p=[n|n<-[2..],i n,i$2*n+1]

```

`i` is a prime check. `p` takes all numbers `n` where both `n` and `2*x+1` are prime. `p` is an infinite list.

Edit: better way for checking if `2*n+1` is prime.

# Answer
> 1 votes
# Julia, 2\*49 - 10 = 88

```
p=primes(2^33)
print(p[map(n->isprime(2n+1),p)])

```

Prints them in list format, `[2,3,5,11,...]`. If that format, using the `primes` function, or waiting until all the computation is done to print isn't acceptable, this prints them one per line as it runs.

```
isprime=f
for i=1:2^33;f(i)&&f(2i+1)&&println(i)end

```

It's a little longer, 52 chars. Both compute all the Sophie Germain primes up to `2^33`, so they should get the 10 point discount.

# Answer
> 1 votes
# Ruby, 61\*2 - 10 = 112

```
require'prime';Prime.each(1.0/0)do|n|p Prime.prime?(n*2+1)end

```

It would take forever to print out all values up to 2\**32

# Edit

Shaved off a few bytes substituting Float::INFINITY for 1.0/0

# Answer
> 1 votes
# Perl, 2\*57-10 = 104

```
use ntheory":all";forprimes{say if is_prime(2*$_+1)}2**33

2
3
5
11
...
8589934091
8589934271

```

42 seconds to 2^32, 1m26s to 2^33. Will run 50% faster if `2*$_+1` is written as `1+$_<<1` but that's one more byte.

The module also installs `primes.pl` which has lots of filters including one for Sophie-Germain primes. So: `primes.pl --so 2**33` (20 bytes)

# Answer
> 1 votes
# PARI/GP, 46 * 2 - 10 = 82

```
forprime(p=2,2^33,if(isprime(2*p+1),print(p)))

```

# Answer
> 1 votes
# Python 3, 2 * 64 bytes - 10 = 118

```
n=1
while 1:n+=1;all((n-~n)*n%k for k in range(2,n))>0!=print(n)

```

Try it online!

It turns out a normal prime test is shorter.

---

# Python 3, 2 * 67 bytes - 10 = 124

```
P=k=1
d=[]
while 1:P*=k*k;k+=1;P%k*k//2in d!=print(k//2);d+=P%k*[k]

```

Try it online!

This uses Wilson's theorem to generate a list of primes. When `k` is prime and `k//2` is prime as well (`in d`), this prints `k//2`.

This can be done a little more memory efficient by not collecting a list of primes but rather doing two prime tests at once at the cost of 4 bytes:

```
P=k=1
m=3;R=4
while 1:P*=k*k;k+=1;R*=m*m*-~m*-~m;m+=2;P%k*R%m>0!=print(k)

```

Try it online!

# Answer
> 1 votes
# Stax, 14 bytes

```
ü♀σJàx╧☺▼∟╓X≥╣

```

Run and debug it

# Answer
> 1 votes
# PowerShell Core, 85 bytes, score 170

```
2
for($i=2){if((&($p={param($a)+!(2..($a-1)|?{!($a%$_)})})(++$i))*(&$p(2*$i+1))){$i}}

```

Try it online!

A bit faster, but longer for 93 bytes

```
for($i=2){if((&($p={param($a)for($u=1;++$u-$a){$k+=!($a%$u)}+!$k})(++$i))*(&$p(2*$i+1))){$i}}

```

# Answer
> 0 votes
# Jelly, 10 bytes =\> score 10

```
ȷ10ÆRḤ‘ẒƊƇ

```

Generates primes up to 10^10 \> 2^32.

Try it online! (TIO link is to a shorter version that generates only up to 1000, so it doesn't time out)

# Answer
> 0 votes
# Pyt, 11 bytes, score 12

```
9ᴇřᵽĐ2*⁺ṗ*ž

```

Try it online!

```
9ᴇřᵽ    generates the first 1,000,000,000 primes (there are 203,280,221 primes less than 2^32)
Đ2*⁺    calculates 2*p+1 for each prime
ṗ       is each 2*p+1 prime
*       multiply the two lists one element at a time
ž       remove all zeroes from list; implicit print

```

# Answer
> 0 votes
# Thunno, \\$ 20 \log\_{256}(96) \approx \\$ 16.46 bytes, score \\$ \approx \\$ 22.92

```
[xNx2*1+N&?xZK((x1+X

```

#### Explanation

```
[                     # while True:
 xN                   #  x is prime?
   x2*1+N             #  x*2+1 is prime?
         &?           #  if both are true:
           xZK        #   print x
              ((      #  endif
                x1+X  #  x=x+1

```

#### Screenshot

# Answer
> 0 votes
# Stax, 10 bytes, score 10

*2\*10=20 score, -10 because it prints infinitely.*

```
▓i☼=ö│╪¥♠p

```

Run and debug it

This is a PackedStax program, which unpacks to the following:

```
VIfc|psH^|pI

```

Run and debug it

# Explanation

```
  f         # filter from 1 to...
VI          # infinity by..
   |p       # is prime
          I # and
  c  sH^    # 2*p+1
        |p  # is prime

```

# Answer
> 0 votes
# Ruby `-rprime`, 34 bytes, score 58

Prints infinitely and should be able to exceed `2**32` due to native support for large numbers, although I haven't bothered to actually wait around to check.

```
Prime.each{p _1 if(2*_1+1).prime?}

```

Attempt This Online! (with a timeout)

---
Tags: code-challenge, primes
---


title: The Rien Number

text:
# Question
Title: The Rien Number
The Champernowne constant is a number that is constructed by concatenating the first `n` numbers, with `n` tending to infinity. It looks something like this:

```
0.123456789101112131415161718192021222324252627282930...

```

Now, I will describe to you the *Rien* number. It can be thought of as a minimization of the Champernowne constant as an integer. I will refer to the *Rien* number with the first `n` digits as Ri(*n*). This is how to formulate it:

1. The first `n` natural numbers (the sequence {1,2,3,...}) are concatenated.
2. This result is then sorted, according to the digit value. So `1..12` would look like `011111223456789`.
3. Since the *Rien* number cannot have leading zeroes, we move all `0`s so that they are significant, whilst keeping the number minimized, resulting in, say, `101111223456789`. This is Ri(*n*), in this case, Ri(12).

Here are some results for Ri(*n*):

```
*n*    Ri(*n*)
1    1
2    12
3    123
7    1234567
9    123456789
10   10123456789
15   101111111223344556789
34   10001111111111111222222222222223333333334444555666777888999
42   100001111111111111122222222222222233333333333333444444455556666777788889999
45   100001111111111111122222222222222233333333333333344444444444555556666777788889999
55   10000011111111111111122222222222222223333333333333333444444444444444455555555555566666777778888899999
100  100000000000111111111111111111112222222222222222222233333333333333333333444444444444444444445555555555555555555566666666666666666666777777777777777777778888888888888888888899999999999999999999
999  100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

```

**Objective** Given a number 1 ≤ `n` \< 10000 as input (via arguments, STDIN, or hardcoding if your language does not support conventional input), output/return Ri(`n`).

This is a , so the shortest code in bytes wins. You may use a language that was made after this contest, as long as it was not made for answering this challenge. (Of course, you *can* use it, if it provides an interesting solution, but mark your answer as non-competing.)

# Reference implementation

I tested this in IE, so there really shouldn't be a problem. If there *is* a problem, there's an easy solution: get a sane browser.

```
function min(n) {
  var seq = [];
  for(var i = 1; i <= n; i++) seq.push(i);
  seq = seq.join("").split("").map(Number);
  var to;
  if(seq.indexOf(1) >= 0) to = seq.splice(seq.indexOf(1), 1);
  seq.sort(function(a, b) {
    return a - b;
  });
  if(to) seq = to.concat(seq);
  return seq.join("");
}
t.onchange = t.onkeyup = function() {
  h.innerHTML = min(this.value)
}
```

```
* {
  font-family: Consolas, monospace;
}
input {
  border: 2px dotted #aaaaaa;
  border-radius: 5px;
  margin: 10px;
}
```

```
<input id="t" type="number">
<div id="h">
```

---

## Leaderboard

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=68685,OVERRIDE_USER=44713;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/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
> 12 votes
# Pyth, 8

```
+1SjktSQ

```

Makes a list `[1, .. , input]` then removes the leading one, joins and sorts, then prepends a 1.

Test Suite

# Answer
> 15 votes
## Perl, ~~44~~ ~~42~~ ~~41~~ ~~33~~ 31 bytes

Yaaay, first post ever !

Thanks to primo for the 2 bytes save.

```
print 1,sort"@{[2..<>]}"=~/\d/g

```

As others did, removing 1 and prepending it manually does the work.

Try it online

# Answer
> 12 votes
# Japt, ~~14~~ 12 bytes

```
1+2o°U ¬¬n ¬

```

Try it online!

### How it works

```
1+2o°U ¬¬n ¬  // Implicit: U = input integer
  2o°U        // Generate the range of integers from 2 to U, inclusive.
       ¬¬     // Join, then split into chars.
         n    // Sort.
1+         ¬  // Join again, and add a 1 to the beginning.
              // Implicit: output last expression

```

# Answer
> 9 votes
## Retina, 78 bytes

Time to show off some new Retina features (it's still not very competitive, but before today this would probably have been closer to 300 bytes).

```
.+
$0$*1
\B
 $`
(1)+
$#1
^1|

.
 1$0$*1
+r`(1+\2) (1+)\b
$2 $1
 1(1)*
$#1
^
1

```

Try it online.

### Explanation

While it's possible to convert between decimal and unary quite conveniently now, this is still quite long because I have to convert back and forth several times because some operations are more doable in decimal than in unary and vice-versa.

```
.+
$0$*1

```

Let's start by converting the input to unary. This works by matching the input and then using `$*1` which repeats `1` that many times (this repetition feature is new as of today).

```
\B
 $`

```

Next, we generate a range from `1` to `N` in unary. I've explained why this works in my FizzBuzz answer.

```
(1)+
$#1

```

We convert each number in the range back to decimal so we can work with the decimal digits. This is done by matching each of the unary numbers such that each `1` generates a separate capture. Then we replace that with the number of captures of group one, using the new capture count syntax `$#1`.

```
^1|

```

This removes the leading `1` as well as all spaces from the string so we're left with only the digits (except for a single `1`).

```
.
 1$0$*1

```

We convert back to unary and add `1` to each digit (to ensure that even `0` is a non-empty). We also insert a space in front of each digit to ensure that they are separated.

```
+r`(1+\2) (1+)\b
$2 $1

```

We repeatedly match a small number preceded by a larger number and swap them. That's bubble sort in Retina. :)

```
 1(1)*
$#1

```

Aaaand back to decimal.

```
^
1

```

Finally, we insert a single `1` at the front to account for the one we've removed earlier.

# Answer
> 6 votes
## Haskell, 44 bytes

```
import Data.List
f n='1':sort(show=<<[2..n])

```

Unfortunately `sort` is in `Data.List`, that's 17 bytes!

# Answer
> 6 votes
# JavaScript (ES6), ~~65~~ ~~62~~ ~~54~~ 52 bytes

*Saved 3 bytes thanks to edc65*

```
x=>eval("for(b='';x>1;)1+[...b+=x--].sort().join``")

```

Builds a string of all numbers from 2 to `x`, then splits, sorts, joins, and adds a 1 to the beginning. This may still be golfable; suggestions welcome!

# Answer
> 5 votes
# CJam, 9

```
1qi),2>s$

```

Try it online

Alternatively:

```
qi,:)(\s$

```

# Answer
> 5 votes
# APL (17)

```
'1',∆[⍋∆←1↓∊⍕¨⍳⎕]

```

Explanation:

```
'1',∆[⍋∆←1↓∊⍕¨⍳⎕]
-----------------
               ⎕   read a number from the keyboard
               ⍳    get the natural numbers up to and including that number
             ⍕¨    get the string representation for each number
           ∊       flatten the array (giving a string of digits)
         1↓        remove the first digit (which is always 1)
       ∆←          store the result in ∆
      ⍋            get a permutation to sort ∆ upwards
    ∆[           ] rearrange ∆ so that it is sorted
'1',               add a 1 to the front

```

Test:

```
      '1',∆[⍋∆←1↓∊⍕¨⍳⎕]
⎕:
      1
1
      '1',∆[⍋∆←1↓∊⍕¨⍳⎕]
⎕:
      10
10123456789
      '1',∆[⍋∆←1↓∊⍕¨⍳⎕]
⎕:
      55
10000011111111111111122222222222222223333333333333333444444444444444455555555555566666777778888899999

```

# Answer
> 5 votes
# Mathematica, 52 bytes

```
"1"<>ToString/@Sort[Join@@IntegerDigits[2~Range~#]]&

```

Once again, string processing happened...

# Answer
> 5 votes
# Bash, ~~35~~ 34 bytes

```
printf %d 1`seq 2 $1|fold -1|sort`

```

This builds on the answers of @DigitalTrauma and @OlivierDulac. Try it online with Ideone.

### How it works

* `seq 2 $1` prints all integers from **2** to the one specified on the command line.
* `fold -1` wraps all lines with width 1, i.e., places each character on its own line.

`-1` seems to be an undocumented feature.
* `sort` sorts the characters by their numeric value.
* `printf %d 1`...`` prepends a **1** to the first line and prints each line as an integer (`%d`), with no separation.

This takes advantage of Bash's curious printf implementation, which repeats the format string over and over, until all arguments are consumed.

# Answer
> 4 votes
# Bash + GNU utilities, 58

```
seq $1|sed 's/./&\n/g'|sort|tr -d \\n|sed 's/\(0*\)1/1\1/'

```

Try it online.

# Answer
> 4 votes
# Jelly, 8 bytes

```
RDFṢ1œ|Ḍ

```

Try it online!

### How it works

```
RDFṢ1œ|Ḍ  Main link. Argument: n (integer)

R         Range; yield r := [1, ..., n].
 D        Convert each k in r into the array of its digits in base 10.
  F       Flatten the resulting array of lists.
   Ṣ      Sort the resulting flat list of digits.
    1œ|   Perform multiset union with 1 as left argument.
          This moves a single 1 to the beginning of the list.
       Ḍ  Convert the resulting list of base 10 to integer.

```

# Answer
> 4 votes
# JavaScript ES6, ~~49~~ 46 Bytes

Thanks to edc65 for 2 bytes

```
F=
x=>1+[...(g=_=>x>1?x--+g``:_)``].sort().join``

;console.log(F(15))
```

# Answer
> 4 votes
# Jelly, 6 bytes

```
ḊVṢ1;Ḍ

```

Try it online!

-1 thanks to Unrelated String

```
Ḋ      # Dequeue (Remove head from implicit range)
 V     # Eval (Jelly stringifies each, concatenates & evals, which does exactly what I want)
  Ṣ    # Sort
   1;  # Prepend a 1
     Ḍ # Decimalify, convert into base-10 number

```

# Answer
> 3 votes
## PowerShell, ~~61~~ 59 bytes

```
param($a)(("1"+-join([char[]]-join(2..$a)|sort)),1)[$a-eq1]

```

Takes input `param($a)` and then uses it to index into an array with `[$a-eq1]`. If true, we index the second element and output `1`. Otherwise, we concatenate `"1"` with the `join`ed array created by 1) defining a new range `2..$a` that has been itself `join`ed together, 2) casting that as a char-array, and 3) sending it through the `Sort-Object` cmdlet, all of which is then output.

Edit1 -- Saved 2 bytes by moving the inner `-join` operator.

# Answer
> 3 votes
## Python 2, 60 bytes

```
_="".join;print"1"+_(sorted(_(map(str,range(2,input()+1)))))

```

# Answer
> 3 votes
# ClojureScript, 48 bytes

```
#(apply str"1"(sort(apply str(range 2(inc %)))))

```

Same as all of the others, pretty much. REPL available here.

# Answer
> 3 votes
## Smalltalk, 76 bytes

As usual in Smalltalk, conceptually very terse, but textually very verbose...

```
f:l^'1',((2to:l)fold:[:p :q|p asString,q asString])asByteArray sort asString

```

Add this as a class method for `String` and call like this, e.g. for 20, `String f: 20`

# Answer
> 3 votes
# Ruby, 48 bytes

An anonymous function. Basically just Rubyfied some of the other answers here..

```
->n{n>1?(?1+[*2..n].join.chars.sort*'').to_i: n}

```

# Answer
> 3 votes
# Milky Way 1.6.4, 22 bytes (not competing)

```
^^'LH=^^JB", "-Q"1";+!

```

I had to add a sorting opcode for this challenge.

---

### Explanation

```
^^                      ` pop the TOS
  '                     ` read input from the command line
   LH                   ` push a reversed Pythonic range(TOS+1)
     =^^J               ` remove the top 2 items from the TOS
         B              ` push the string literal of the TOS
          ", "-         ` remove ", " from the TOS
               Q        ` sort the TOS
                "1";+   ` add "1" to the beginning of the TOS
                     !  ` output the TOS

```

# Answer
> 3 votes
## MATL, 17 bytes

Uses current version (7.0.0) of language/compiler.

```
49[]i:"@YUh]6L)Sh

```

Inspired by FryTheEgggman's answer.

*EDIT (July 29, 2016): You can try it online with some modifications to conform to changes in the language.*

### Example

```
>> matl
 > 49[]i:"@YUh]6L)Sh
 >
> 12
101111223456789

```

### Explanation

```
49        % push '1'
[]        % push empty array
i:        % input "N" and build vector [1, 2, ... N]
"         % for each number in this vector
   @      % push that number
   YU     % convert to string
   h      % concatenate horizontally
]         % end
6L)       % remove first element
S         % sort
h         % concatenate horizontally

```

# Answer
> 3 votes
# Brachylog, ~~76~~ 41 bytes

```
1 .;{,1:.e?}?:1fcbZlL,ZoOlM,10^(L-M)=:Oc.

```

Takes a number as input.

This solution works with the few changes I made to the built-in Findall predicate `f`. OP is apparently OK with using languages older than the answer so I think this is fine (the changes I made were intented a long time ago, I just motivated myself to do it because of this challenge).

### Explanation

```
1 .                                            § If the input is 1, unify output with 1

   ;                                           § Else

    {      }?:1f                               § Output a list of all inputs which satisfy
                                               § the predicate in brackets with the input
                                               § of the main predicate (ie the input number)
                                               § as output

     ,1:.e?                                    § True if the input is an integer between 1
                                               § and . (the output)

                cbZ                            § Concatenate everything into a single number,
                                               § remove the first digit (1) and call it Z

                   lL,ZoOlM,                   § L is the length of Z, M is the length of O
                                               § O being Z sorted (which removes the leading
                                               § 0s)

                            10^(L-M)=:Oc.      § Concatenate 10^(L-M) at the beginning of O
                                               § and unify it with the output

```

# Answer
> 3 votes
# Bash and GNU tools, ~~58~~ 52 bytes

```
echo 1$(seq 2 $1|sed -e 's/./&\n/g'|sort|tr -d \\n)

```

# Answer
> 3 votes
# Gogh, ~~9~~ 7 bytes

```
GJT1-1P

```

You can run this using:

```
$ ./gogh noi 'GJT1-1P' <input>

```

---

```
G     “ Push a range (1, TOS]       ”
J     “ Join the TOS                ”
T     “ Sort the TOS                ”
1-    “ Remove the first 1          ”
P     “ Prepend the TOS to the STOS ”

```

# Answer
> 3 votes
# Oracle SQL 11.2, ~~222~~ 211 bytes

```
SELECT 1||TRIM(xmlagg(xmlelement(e,c)).EXTRACT('//text()'))FROM(SELECT SUBSTR(s,LEVEL+2,1)c FROM(SELECT MAX(sys_connect_by_path(LEVEL,' '))s FROM DUAL CONNECT BY LEVEL<=:1)CONNECT BY LEVEL<=LENGTH(s)ORDER BY 1);

```

Un-golfed

```
SELECT 1||TRIM(xmlagg(xmlelement(e,c)).EXTRACT('//text()'))  -- add leading 1, concatenate each char and remove spaces
FROM   (
         SELECT SUBSTR(s,LEVEL+2,1)c                          -- split the string in characters, omiting the first number (1)
         FROM   (
                  SELECT MAX(sys_connect_by_path(LEVEL,' '))s -- create a string by concatenating numbers
                  FROM   DUAL
                  CONNECT BY LEVEL<=:1
                )
         CONNECT BY LEVEL<=LENGTH(s)ORDER BY 1
       )

```

# Answer
> 3 votes
# Vyxal `R`, 4 bytes

```
ḣṅs+

```

Try it Online! -2 thanks to Lyxal.

```
ḣ    # Implicitly convert to [1...n], then push 1 and [2...n]
 ṅ   # Concatenate [2...n] into a string
  s  # Sort
   + # Prepend the 1 from before

```

# Answer
> 3 votes
# TI-Basic, 77 bytes

```
Input N
{0
For(I,2,N
augment(Ans,int(10fPart(I/seq(₁₀^(J),J,1,1+int(log(I
End
Ans→A
SortD(ʟA
1→ʟA(dim(ʟA
.1sum(seq(₁₀^(I)ʟA(I),I,1,dim(ʟA

```

Output is stored in `Ans` as a number and is displayed. Does not work for inputs that are 55 and above because of overflow errors.

---

### 87 bytes

```
Input N
{0
For(I,2,N
augment(Ans,int(10fPart(I/seq(₁₀^(J),J,1,1+int(log(I
End
Ans→A
SortA(ʟA
"1
For(I,2,dim(ʟA
Ans+sub("0123456789",ʟA(I)+1,1
End

```

Output is stored in `Ans` as a string. Works with higher inputs than the above method could, depending on how much free RAM there is. `sub("0123456789",ʟA(I)+1,1` can be replaced with `toString(ʟA(I` to save 18 bytes if it is run on a TI-84+ CE OS 5.2+.

# Answer
> 3 votes
# Nekomata, 8 bytes

```
RtƊjo1cɗ

```

Attempt This Online!

```
RtƊjo1cɗ
R           Range [1, input]
 t          Tail; remove the first element
  Ɗ         Convert to lists of decimal digits
   j        Join
    o       Sort
     1c     Prepend 1
       ɗ    Convert from a list of decimal digits

```

# Answer
> 2 votes
# Julia, 33 bytes

```
n->"1"*join(sort([join(2:n)...]))

```

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

We construct the range `2:n`, which will be empty for `n` \< 2, join it into a string, splat the string into an array of characters, sort them, join it into a string, and prepend 1.

# Answer
> 2 votes
# APL, 21 bytes

```
{' '~⍨⍕1,x[⍋x←⍕1↓⍳⍵]}

```

This is an unnamed monadic function that accepts an integer on the right and returns a string. To call it, assign it to a variable.

Explanation:

```
            x←⍕1↓⍳⍵]}   ⍝ Get the numbers 1:input, drop 1, convert to string
         x[⍋            ⍝ Sort
      ⍕1,               ⍝ Tack 1 onto the front, flatten to string
{' '~⍨                  ⍝ Remove the spaces (side effect of ⍕ on an array)

```

Try it online

# Answer
> 2 votes
# Python 2, 60 bytes

```
P=input();print"1"+"".join(sorted(`range(2,P+1)`)[P*2-4:-2])

```

Indexing for the win. :-)

---

# Python 2, 60 bytes

```
P=input();print"1"+"".join(sorted(`range(-P,-1)`))[P*3-5:-2]

```

Just an alternative.

# Answer
> 2 votes
## Seriously, 10 bytes

```
,u2xεjS'1+

```

Hex Dump:

```
2c753278ee6a5327312b

```

Try It Online

Explanation:

```
,            Read input
 u2x         Push range from 2..n
    εj       Join into string
      S      Sort
       '1+   Prepend a "1"

```

# Answer
> 2 votes
# 05AB1E, 6 bytes

**Note:** This submission uses features that postdate this challenge and is therefore not competitive

Code:

```
Lß?J{?

```

Explanation:

```
L      # Creates the list [1 .. input]
 ß     # Extract the smallest value of the list
  ?    # Print this value (always 1)
   J   # ''.join(list)
    {  # Sort the string
     ? # Print this value

```

Uses ISO 8859-1 encoding

# Answer
> 2 votes
# Mathcad, 86 "bytes"

The function s(n) uses a for loop to build up the Champernowne "integer" by converting each number to its string form and concatenating them together. The string is then converted to its equivalent vector of ASCII codes and sorted. The function then swaps any leading zeros with the first one, finally converting the vector back to a string.

To check the function, I put the test cases into a vector vn, then applied s to vn using the vectorize operator. I then check the results against the given test case values.

---

Mathcad is mathematical application based on 2D worksheets comprised of "regions" each of which can be text, a mathematical expression, program, plot or scripted component.

A mathematical or programming instruction is picked from a palette toolbar or entered using a keyboard shortcut. For golfing purposes, an operation ("byte") is taken to be the number of keyboard operations necessary to create a name or expression (for example, to set the variable a to 3, we would write a:=3. The definition operator := is a single keypress ":", as are a and 3 giving a total of 3 "bytes". The programming for operator requires typing ctl-shft-# (or a single click on the programming toolbar) so again is equivalent to 1 byte.

# Answer
> 2 votes
# Reng v.3.2, 36 bytes

```
1i#x:xe!Ø;$:1+)å(Eh
å'11µ1nran! ¡n~

```

Try it here!

This pushes `1` to the stack, then stores the input `i` into `x` (`i#x`). Then, a range of all the necessary numbers is created using `:xe!Ø;$:1+)å(Eh`, being ended by `Ø`, which goes the first i.e. next line. `å` takes every number and pushes the digits of that number.

On the next line, `å` breaks the last number into its digits, `'` sorts the stack, and `11µ` removes 1 `1` from the stack. A `1` is then printed, and the numbers are reversed then outputted through the loop `an! ¡n`. The program is terminated with `~`.

# Answer
> 2 votes
## Seriously, 10 bytes

```
,Rp@εjS@$+

```

Try it online!

Explanation:

```
,Rp@εjS@$+
,Rp@        push range(1, input()+1), pop first element (1), swap
    εjS     join list on empty string, sort
       @$+  prepend the 1

```

# Answer
> 2 votes
## Pyke, 9 bytes, noncompetitive

```
Stm`sS1R+

```

Explanation:

```
S         -      range(1,inp+1)
 t        -     ^[1:]
  m`      -    map(str,^)
    s     -   sum(^)
     S    -  sort(^)
      1R+ - 1+^

```

Try it here!

# Answer
> 2 votes
# Stacked, 22 bytes

```
2\|>''join sorted'1'\+

```

Try it here! Expects input on TOS. Example on the repl:

```
> 15
(15)
> 2\|>''join sorted'1'\+
('101111111223344556789')

```

## Explanation

```
2\|>''join sorted'1'\+
2\|>                    range from 2 to n
    ''join              join by empty string
           sorted       sort it
                 '1'\+  and prepend a '1'

```

A more fun version:

## Stacked, 45 bytes

```
{*x:1[1+:yield]x 1-*}!toarr''join sorted'1'\+

```

Expects input as TOS. For example (on the repl):

```
> 15    (* the input *)
(15)
> {*x:1[1+:yield]x 1-*}!toarr''join sorted'1'\+
('101111111223344556789')
>

```

### Explanation

```
{*x:1[1+:yield]x 1-*}!toarr''join sorted'1'\+
{*x:1[1+:yield]x 1-*}                            generator function that...
  x:                                               given x
    1                                              pushes 1
     [        ]x 1-*                               and executes the inside (x-1) times:
      1+                                             adds 1 to the TOS (initially 1);
                                                     2 is the first value yielded
        :yield                                       and yields it for the generator
                     !                           initialize this generator with TOS
                      toarr                      exhaust generator into an array
                           ''join                join by empty strings
                                  sorted         sort the values
                                        '1'\+    prepend '1'.

```

# Answer
> 2 votes
# C (gcc), ~~172~~ ~~161~~ ~~158~~ 156 bytes

* Saved ~~eleven~~ ~~fourteen~~ sixteen bytes thanks to ceilingcat.

```
f(n){char*z,s[++n];int d[10]={0},j=1,k=0;for(;sprintf(s,"%d",j),j++<n;)for(z=s;*z;)d[*z++-48]++;for(d[printf("1")]--;k<10;)for(j=d[k++];j--;putchar(k+47));}

```

Try it online!

# Answer
> 2 votes
# Japt, 8 bytes

```
ô ¤¬ñ i1

```

Try it

```
ô ¤¬ñ i1     :Implicit input of integer
ô            :Range [0,input]
  ¤          :Slice off the first 2 elements
   ¬         :Join
    ñ        :Sort
      i1     :Prepend 1

```

# Answer
> 2 votes
# Thunno 2 `O`, 5 bytes

```
RḢ¢JṠ

```

Try it online!

#### Explanation

```
RḢ¢JṠ  # Implicit input
R      # Push the range [1..input]
 Ḣ     # Extract first item (1)
  ¢    # Print without newline
   J   # Join the list
    Ṡ  # Sort the resulting string
       # Implicit output

```

# Answer
> 1 votes
## Lua, 102 Bytes

How can lua be so long while all other entries are \< 30 bytes... I'm sure even Java would be shorter!

```
t={}for i=2,...do(i..''):gsub(".",function(d)t[#t+1]=d end)end
table.sort(t)print(1 ..table.concat(t))

```

### Ungolfed

```
t={}                           -- initialise t as a table
for i=2,...                    -- iterate from 2 to n
do
  (i..''):gsub(".",function(d) -- iterate over each digits in i
    t[#t+1]=d                  -- insert the digit into t
  end)
end
table.sort(t)                 -- sort t
print(1 ..table.concat(t))    -- prepend a 1 to the content of t separated by ''

```

I'm forced to put a space in `print(1 ..`, else it would try to evaluate it to a decimal `1.<decimal part>`, and throws an error because `.` isn't a valid decimal part.

# Answer
> 1 votes
# Attache, 20 bytes

```
{"1"+Sort!Join[2:_]}

```

Try it online!

The point-free version is actually 1 byte longer: `"1"&`+@Sort@Join@2&`:`. This works as most of the other answers do.

# Answer
> 1 votes
# Husk, 8 bytes

```
:'1Oṁs…2

```

Try it online!

Corrected my previous answer.

# Answer
> 1 votes
# Java (JDK), ~~153~~ 151 bytes

```
i->{var s="";for(int j=0;j++<i;)s+=j;var c=s.toCharArray();java.util.Arrays.sort(c);return new String(c).replaceFirst("1","0").replaceFirst("^.","1");}

```

Try it online!

-2 Thanks to Ceilingcat!

# Answer
> 1 votes
# Ly, 19 bytes

```
n[sSl,]ppar1y[fu,]p

```

Try it online!

```
n                    - read count of numbers to use from STDIN
 [s l,]              - loop that many times, using backup cell to save loop var
   S                 - push digits of "int" at the top of the stack
       pp            - drop "0" and "1" from the stack
         ar          - sort digits, reverse stack
           1         - push "1" onto the stack
            y        - push the stack size onto the stack
             [  ,]   - loop over over stack, use backup cell for loop var
              fu     - flip loop var and digit, print digit
                  p  - delete loop var

```

# Answer
> 1 votes
# R, 60 bytes

```
a=\(n)cat(1,sort(unlist(strsplit(c("",1:n)[-2],""))),sep="")

```

# Answer
> 1 votes
# PowerShell Core, 44 bytes

```
"1"+-join(1.."$args"-ne1|%{"$_"|% t*y}|sort)

```

Try it online!

```
"1"+-join(1.."$args"-ne1|%{"$_"|% t*y}|sort)
"1"+                                          # Always return a 1
          1.."$args"-ne1|%{"$_"|% t*y}|sort   # Generate a range from 2 to the $a, convert to characters, sort them
    -join(                                 )  # Join them into a string

```

Created with the help of Luminespire.

# Answer
> 1 votes
# Raku, 46 bytes

```
{{S/(0*)(.)/$1$0/}([~] ([~] 1..$_).comb.sort)}

```

Try it online!

# Answer
> 0 votes
# Ruby, 73 bytes

```
n,s=gets.to_i,"";(2..n).each{|i|s+=i.to_s};p ("1"+s.chars.sort.join).to_i
```

Attempt This Online!

---
Tags: code-golf, math, number, sequence, sorting
---


title: Motzkin Numbers

text:
# Question
Title: Motzkin Numbers
The nth Motzkin Number is the number of paths from (0, 0) to (n, 0) where each step is of the form (1, -1), (1, 0) or (1, 1), and the path never goes below y = 0.

Here's an illustration of these paths for n = 1, 2, 3, 4, from the above link:

The desired sequence is OEIS A001006. OEIS has some other characterizations of the sequence.

---

You will be given a positive integer n as input. You should output the nth Motzkin Number.

Here are Motzkin numbers 1 to 10:

```
1, 2, 4, 9, 21, 51, 127, 323, 835, 2188

```

---

All standard input and output methods are allowed. Standard loopholes apply.

This is code golf. Fewest bytes wins.

# Answer
# MATL, 13 ~~14~~ bytes

```
i-2/t.5+hH4Zh

```

### Example:

```
>> matl i-2/t.5+hH4Zh
> 6
51

```

*EDIT (June 16, 2017): you can **try it online!** Note also that in modern versions of the language (that post-date this challenge) the `i` could be removed.*

### Explanation

Pretty straightforward, using the equivalence (see equation (10)) with the hypergeometric function:

$$M\_n = {}\_2F\_1 \left( \frac {1-n} 2, -\frac n 2 ; 2 ;4 \right)$$

From the definition of the hypergeometric function

$${}\_2F\_1(a,b; c; z) = \sum ^ \infty _ {n=0} \frac {(a)\_n (b)\_n} {(c)\_n} \frac {z^n} {n!}$$

it's clear that the order of the first two arguments can be interchanged, which saves one byte.

```
i         % input
-2/       % divide by -2
t.5+      % duplicate and add 0.5
h         % horizontal concatenation into a vector
H         % number 2
4         % number literal
Zh        % hypergeometric function with three inputs (first input is a vector)

```
> 15 votes

# Answer
## Retina, ~~59~~ 58 bytes

```
+`(\D*)1(1*)
:$1<$2:$1>$2:$1_$2:
:(_|()<|(?<-2>)>)+:(?!\2)

```

Takes input in unary. Input 7 (i.e. `1111111`) takes quite a while but still completes in less than a minute. I wouldn't go much further than that.

Try it online.

### Explanation

A different characterisation of the Motzkin numbers is the number of strings of three different characters, where two of them are correctly balanced (hence the close relation to Catalan numbers, which are the same without the third character which is independent of the balancing).

.NET's balancing groups are pretty good at detecting correctly matched strings, so we simply generate *all* strings of length `N` (using `_`, `<` and `>` as the three characters) and then we count how many of those are correctly balanced. E.g. for `N = 4` the valid strings are:

```
____
__<>
_<_>
_<>_
<__>
<_>_
<>__
<<>>
<><>

```

Compared with the definition in the challenge, `_` corresponds to a `(1,0)` step, `<` to `(1,1)` and `>` to `(1,-1)`.

As for the actual code, the `:` is used as a separator between the different strings. The second regex is just a golfed form of the standard .NET regex for balanced strings.

Something to note is that there is only a single `:` inserted between strings in each step, but the second regex matches a leading *and* a trailing `:` (and since matches cannot overlap, this means that adjacent strings generated from one template in the last step cannot both match). However, this is not a problem, because at most one of those three can ever match:

* If the string ending in `_` matches, the prefix without that `_` is already balanced correctly, and `<` or `>` would throw off that balance.
* If the string ending in `>` matches, the string is balanced *with* that `>`, so `_` or `<` would throw off that balance.
* Strings ending in `<` can never be balanced.
> 11 votes

# Answer
## Python 2, 51 bytes

```
M=lambda n:n<1or sum(M(k)*M(n-2-k)for k in range(n))

```

Uses the formula from Mathworld

Saves chars by putting the `M[n-1]` term into the summation as `k=n-1`, which gives `M[-1]*M[n-1]`, with `M[-1]=1` as part of the initial condition.

Edit: One char shorter writing the sum recursively:

```
M=lambda n,k=0:n<1or k<n and M(k)*M(n-2-k)+M(n,k+1)

```

Other approaches that turned out longer:

```
M=lambda n,i=0:n and(i>0)*M(n-1,i-1)+M(n-1,i)+M(n-1,i+1)or i==0
M=lambda n:+(n<2)or(3*~-n*M(n-2)+(n-~n)*M(n-1))/(n+2)

```
> 10 votes

# Answer
# Pyth, 15 bytes

```
Ls*V+KyMb1+t_K1

```

This defines a function `y`. Try it online: Demonstration

### Explanation:

Let `y[n]` be the `n`-th Motzkin Number. I calculate `y[n]` with the formula

```
y[n] = dot product of (y[0], ..., y[n-1], 1) and (y[n-2], ..., y[0], 1)

```

Notice that the first vector is larger than the second one (except when calculating `y[0]`). When this is the case, than Pyth automatically ignores the 1 at the end of the first vector, so that both vectors are of equal length.

```
Ls*V+KyMb1+t_K1
L                 define a function y(b), which returns:
      yMb            compute the list [y[0], y[1], ..., y[b-1]]
     K               assign it to K
  *V                 vectorized multiplication of
    +K   1             * K with a 1 at the end
          +t_K1        * reverse(K), remove the first element, and append 1
 s                   return the sum (dot product)

```

This formula is a variation of one of the formulas listed on OEIS. It may be a little bit stupid. Because of the 1 at the end of the first vector (which make the lengths unequal), I don't actually have to give the recursion a base case. And I had hopes, that the two `+...1`s can be golfed somehow. Turns out I can't.

You can define a similar recursion with a dot product of equal length vectors and define the base case `y[0] = 1` with with the same byte count.
> 8 votes

# Answer
## CJam (20 bytes)

```
.5X]{__W%.*:++}qi*W=

```

Online demo

As Mego noted in the comments on the question, this is very closely related to the Catalan numbers: change the `.5` to `1` and offset the index by one (or simply remove the `.5` entirely and leave the index unchanged) to get Catalan numbers.

The recurrence used is

> a(n+2) - a(n+1) = a(0)\*a(n) + a(1)\*a(n-1) + ... + a(n)\*a(0). \[Bernhart\]

from the OEIS page. The corresponding recurrence for the Catalan numbers is listed as

> a(n) = Sum\_{k=0..n-1} a(k)a(n-1-k).
> 7 votes

# Answer
## Seriously, 21 bytes

```
,;╗r`;τ╜█@;u@τ╣║\*`MΣ

```

Borrows some code from quintopia's Catalan Numbers solution, specifically the improvement I made in the comments.

I use the following formula:

Since `nCk` is 0 for `k > n`, I sum all the way to `n-1`, since those values will all be 0 and thus do not affect the sum.

Try it online

Explanation:

```
,;╗r`;τ╜█@;u@τ╣║\*`MΣ
,;╗                    push input, dupe, store one copy in register 0
   r                   push range(0, n) ([0,n-1])
    `             `M   map the function:
     ;τ╜█@               dupe k, push C(n, 2*k), swap with k
          ;u@τ╣║\        push the kth Catalan number
                 *       multiply
                    Σ  sum

```
> 6 votes

# Answer
# R, 64 bytes

```
f=function(n)ifelse(n<2,1,f(n-1)+sum(rev(s<-sapply(2:n-2,f))*s))

```

Uses also the Mathworld formula of @xnor's python answer. Thanks to rules of precedence, `2:n-2` is equivalent to `0:(n-2)`.

Test cases:

```
> f(0)
[1] 1
> f(1)
[1] 1
> f(5)
[1] 21
> f(10)
[1] 2188
> sapply(0:20,f)
 [1]        1        1        2        4        9       21       51      127
 [9]      323      835     2188     5798    15511    41835   113634   310572
[17]   853467  2356779  6536382 18199284 50852019

```
> 5 votes

# Answer
# Mathematica, ~~31~~ 30 bytes

```
AppellF1[-#/2,.5,-#/2,2,4,4]&

```

For fun, here's a 37 byte version

```
Hypergeometric2F1[(1-#)/2,-#/2,2,4]&

```

and 52 byte version

```
SeriesCoefficient[1-x-Sqrt[1-2x-3x^2],{x,0,#+2}]/2&

```
> 5 votes

# Answer
# Jelly, ~~17~~ ~~14~~ 13 bytes

```
×US;
1;HÇƓ¡1ị

```

This uses the recurrence relation from @PeterTaylor's answer. Try it online!

### How it works

```
×US;      Define a helper link. Left argument: a (list)

×U        Multiply (×) a by its reverse (U).
  S       Compute the sum of the resulting list.
   ;      Prepend it to a.
          Return the result.

1;HÇƓ¡1ị  Define the main link.

1         Set the left argument to 1.
 ;H       Append the half of 1 to 1. Result: [1, 0.5].
    Ɠ     Read an integer n from STDIN.
   Ç ¡    Call the helper link (Ç) n times.
      1ị  Retrieve the result at index 1.

```
> 4 votes

# Answer
# Mathematica, ~~44~~ ~~42~~ 34 bytes

```
Sum[#!/(i!(i+1)!(#-2i)!),{i,0,#}]&

```

A 35 bytes version:

```
Coefficient[(1+x+1/x)^#,x]/#&[#+1]&

```
> 3 votes

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

```
ÝI<ãʒ.øDŸQ}g

```

Try it online!

While most answers use a formula or recurrence relation, this is a simple counting approach.

Each possible path through the grid is represented by the list of its y coordinates. For n segments, there are a total of (n+1) points, but the first and last one are necessarily 0, so that leaves (n-1) points to specify.

```
Ý           # range [0..n]
 I<         # n - 1
   ã        # cartesian power

```

We now have a list of paths (not yet including the initial and final 0). By construction, none of them ever go below 0. However, some of them have illegal slopes (e.g. jump from 0 to 2), so we need to filter them out.

```
ʒ      }g   # count how many paths satistfy the following condition
 0.ø        # surround with 0
      Q     # is equal to
    DŸ      # its own fluctuating range

```

`Ÿ` is the fluctuating range built-in. If there's any pair of non-adjacent numbers, it will fill in the missing numbers (e.g. \[0, 2\] becomes \[0, 1, 2\]). Only legal paths will be left unchanged.

A perhaps more intuitive way to check for illegal slopes would be `üαà` (assert the maximum of pairwise absolute differences equals 1). However, this misses the flat \[0, 0, ... 0\] path, which costs one extra byte to fix.

Finally, note that the actual code uses  where this explanation uses `0.ø`. Instead of surrounding the path with 0s, this surrounds the implicit input with two copies of the path. This turns the coordinate system upside-down and inside-out, but is otherwise equivalent.
> 3 votes

# Answer
# Stax, 12 bytes

```
îu¬@Y≤ÅÉÑ(πε

```

Run and debug it

I don't know how to do fancy math typesetting, but this essentially relies on a dynamic programming construction

```
M(0) = 1
M(1) = 1
M(n + 1) = M(n) + sum(M(k) * M(n - k - 1) for k in [0..n-1])

```
> 3 votes

# Answer
# Pari/GP, ~~38~~ ~~36~~ 26 bytes

```
n->(1+x+x^2)^n++/n\x^n++%x

```

Try it online!

Using equation (11) from MathWorld:

\\$ M\_n = \dfrac{1}{n + 1} \dbinom{n + 1}{1}\_2 \\$

where \\$ \binom{n}{k}\_2 \\$ is a trinomial coefficient. By definition, \\$ \binom{n}{k}\_2 \\$ is the coefficient of \\$ x^{n + k} \\$ in the expansion of \\$ (1 + x + x^2)^n \\$.
> 2 votes

# Answer
# Ruby, 50

straightforward implementation of the recurrence relation.

```
g=->n{n<2?1:(3*(n-1)*g[n-2]+(2*n+1)*g[n-1])/(n+2)}

```
> 1 votes

# Answer
# Haskell, ~~55~~ 52 bytes

Straightforward implementation of the recursion. Thanks @Delfad0r for -3 bytes!

```
a n|n>2=div((2*n+1)*a(n-1)+(3*n-3)*a(n-2))$n+2
a n=n

```

Try it online!
> 1 votes

# Answer
# Brain-Flak, 90 bytes

```
(([{}]<(())>)<{({}()<{<>([({})]({}[({})]({}<>{}<>)))<>}<>>)}>){({}()<{}>)}{}({}{}[{}{}]<>)

```

Try it online!

Computes \\${\binom{n}{0}}\_2 - {\binom{n}{2}}\_2\\$, where \\$\binom{n}{k}\_2\\$ is a trinomial coefficient. I couldn't find this formula anywhere, so I can't reference it, but it can be proved in the same way as the analogous formula \\$C\_n = \binom{2n}{n} - \binom{2n}{n+1}\\$.
> 1 votes

# Answer
# Maxima, 49 bytes

Use the formula

\\$ M\_n=\frac{1}{n+1}\cdot\[z^{n+2}\](1+x+x^2)^n \\$

```
f(n):=coeff(expand((1+x+x^2)^(n+1)),x,n+2)/(n+1);

```

Try it online!
> 1 votes

# Answer
## ES6, 44 bytes

```
f=(n,k=0)=>n<1?1:k<n&&f(k)*f(n-2-k)+f(n,k+1)

```

Straightforward port of @xnor's recursive Python solution. Needs `n<1?1:` because `n<1||` would make `f(0)` return `true`.
> 0 votes

# Answer
# Nekomata \+ `-n`, 8 bytes

```
3$ŧ←∫Ɔž≥

```

Attempt This Online!

```
3$ŧ←∫Ɔž≥    Let n be the input
3$ŧ         Find an n-tuple of integers in [0, 3)
   ←        Decrement each element
    ∫       Take the cumulative sum
     Ɔž     Check that the last element is 0
       ≥    And that each element is non-negative

```

`-n` counts the number of solutions.
> 0 votes

---
Tags: code-golf, number, sequence, combinatorics, balanced-string
---


title: Output all strings

text:
# Question
Title: Output all strings
Given a set of letters, output all strings made of those letters. (This is Kleene star of the set.) For example, for `{'a','b'}`, the strings are:

```
'', 'a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa', 'aab', ...

```

**Input:** A non-empty collection of distinct letters `a..z`. These may be characters or single-character strings.

**Output:** All strings in those letters, in any order, without repeats. You may use lists of chars as strings.

This is an infinite list, so you can output it by:

* Running forever writing more and more strings. These strings can be written in any flat separated format, meaning that they you can tell where each string ends, but the strings aren't subdivided into groups.
* Taking a number `n` as input and outputting the first `n` strings in any flat separated format
* Yielding each string in turn from a generator object
* Producing an infinite object

Be sure that your method eventually produces every string in the output, since it's possible to produce infinitely many strings from the set while never getting to some strings.

You may **not** output it by

* Producing the `n`th string given `n`
* Providing a membership oracle that decides if a given string belongs to the set

Built-ins are allowed, but I ask voters to give attention to answers that implement the operation themselves over ones that mostly rely on a built-in.

```
var QUESTION_ID=74273,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/74273/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
# Python 2, 53 ~~56~~

-3 after realizing that `yield x` can be used as an expression.

```
def f(s):yield'';[(yield w+c)for w in f(s)for c in s]

```
> 26 votes

# Answer
# Haskell, 24 bytes

```
f s=[]:[b:a|a<-f s,b<-s]

```

Produces an infinite list.

```
*Main> f "abc"
["","a","b","c","aa","ba","ca","ab","bb","cb","ac","bc","cc","aaa","baa","caa","aba","bba","cba",…

```
> 22 votes

# Answer
# Mathematica, ~~32~~ 31 Bytes

```
Do[Echo/@#~Tuples~n,{n,0,∞}]&

```

# Edit:

CatsAreFluffy scraped off one byte.
> 10 votes

# Answer
## JavaScript (ES6), 61 bytes

```
function*g(s){yield'';for(let r of g(s))for(c of s)yield c+r}

```

Port of @feersum's Python generator. The `let` is necessary. Save 2 bytes by using an array comprehension (failed ES7 proposal, but works in Firefox 30-57):

```
function*g(s){yield'';[for(r of g(s))for(c of s)yield c+r]}

```

Alternative version for 73 bytes that returns the first `n` elements yielded by the above generator:

```
(s,n)=>Array(n).fill('').map(g=(r,i)=>i--?g(r+s[i%l],i/l|0):r,l=s.length)

```
> 10 votes

# Answer
# Perl, ~~39~~ ~~37~~ 35 bytes

(First describes an older version. The new shorter program is at the end)

Includes +3 for `-alp`

Run with the set of characters on STDIN, e.g. `perl -alp kleene.pl <<< "a b c"`

`kleene.pl` (this version is 34+3 bytes):

```
$#a=$"=","}for(@a){push@a,<{@F}$_>

```

Add +2 for `-F` (drop implicit `-a` if no spaces between input characters, or -6 (only `@a=""` before `}`) if we already put commas between the characters on STDIN

## Explanation:

The `-alp` options make the code effectively:

```
BEGIN { $/ = "\n"; $\ = "\n"; }
LINE: while (defined($_ = <ARGV>)) {
    chomp $_;
    our @F = split(' ', $_, 0);
    $#a = $" = ',';
}
foreach $_ (@a) {
    use File::Glob ();
    push @a, glob('{' . join($", @F) . '}' . $_);
}

```

As you can see `<>` in perl is not only used for readline, but can also do shell style globbing (in fact in ancient perls it was implemented by calling the shell).

For example `<{a,b}{1,2}>` will expand to `"a1","a2","b1","b2"`

So if we have the elements in `@F` we just need to add commas inbetween. The default inbetween character for interpolation is space, which is stored in special variable `$"`. So setting `$"` to `,` will turn `"{@F}"` into `{a,b}` if `@F=qw(a b)` (globs expand as strings)

In fact I would really have liked to loop with something like `glob"{@F}"x$n++`, but I kept running into the problem that the first empty line doesn't get generated and all workarounds I found made the code too long.

So another essential part of this code is that if you use a `for` to loop over an array you can actually push extra elements on it during the loop and the loop will also pick up these new elements. So if in the loop we are e.g. at element `"ab"`, then `<{@F}$_>` will expand to `<{a,b}ab>` which in list context becomes `("aab", "bab")`. So if I push these on `@a` then the strings extended one to the left become available too

All I still need to do is prime the loop with an empty string. That is done using`$#a = 0` (`,` in numeric context becomes `0`) which causes the first and only element of `@a` to become undef which will behave like `""` when I use it

## Improvement

In fact by doing tests for this explanation I found a short way to use a growing glob that properly handles the first empty entry. Run as `perl -ap kleene0.pl <<< "a b"` (so add 2 bytes for `-ap`)

`kleene0.pl` (this version is 33+2 bytes):

```
$"=",";print<$z,>;$z.="{@F}";redo

```

All these solutions will keep more and more of the output in memory and that will cause the program to fail after some time. You can also use perl globs for lazy generation by using them in scalar context, but that makes the programs longer....
> 8 votes

# Answer
# Jelly, ~~8~~ 6 bytes

```
⁷³p$Ȯ¿

```

Try it online!

### How it works

```
⁷³p$Ȯ¿    Monadic link. Argument: A (alphabet)

⁷         Set the return value to '\n'.
     ¿    While loop.
            Condition:
    Ȯ         Print the current return value and return it (always truthy).
            Body:
   $          Combine the two links to the left into a single, monadic link.
 ³              Yield A.
  p             Perform the Cartesian product of A and the current return value,
                updating the return value in the process.

```

## Alternate version, 6 bytes

```
R’ḃL}ị

```

This is a dyadic link that accepts an alphabet and the desired number of strings as left and right arguments, respectively.

Try it online!

### How it works

```
R’ḃL}ị    Dyadic link. Arguments: n (integer), A (alphabet)

R         Range; yield [1, ..., n].
 ’        Decrement; yield [0, ..., n-1].
   L}     Yield l, the length of A.
  ḃ       Convert every i in [0, ..., n-1] to bijective base l.
     ị    For each array of digits, retrieve the corresponding characters of A.

```
> 6 votes

# Answer
# Pyth, 7

```
<s^LzQQ

```

Try it here

This computes the cartesian product of the input with each number from `0..n-1`, joins them, and then only keeps the first `n`. This will time out online for numbers or strings that are much bigger than 3-4.

Alternatively, to get infinite output look at Jakube's answer.
> 6 votes

# Answer
## CJam, ~~16~~ 10 bytes

*Thanks to jimmy23013 for saving 6 bytes.*

```
N{eam*_o}h

```

Input is one command-line argument per character. Output is one string on each line.

Try it online! (But kill it immediately...)

### Explanation

```
N      e# Push [\n]. At each step this array will contain all strings of length N,
       e# each followed by a linefeed.
{      e# Infinite loop...
  ea   e#   Read command-line arguments.
  m*   e#   Cartesian product: pairs each letter with each string in the list.
  _o   e#   Output all the strings of the current length.
}h

```
> 4 votes

# Answer
# Python 2, ~~89~~ ~~84~~ 83 bytes

```
x,n=input()
l=len(x)
for i in range(n):
 s=''
 while i:i-=1;s+=x[i%l];i/=l
 print s

```
> 4 votes

# Answer
# Nekomata, 2 bytes

```
Ňŧ

```

Attempt This Online!

```
Ňŧ
Ň       Nondeterministically choose an natural number, say n
 ŧ      Nondeterministically choose a tuple of n elements from the input list

```

In the default mode, Nekomata prints all possible outputs.
> 4 votes

# Answer
# Pyth, 7 bytes

```
.V0j^zb

```

Alternative to @fry. This program reads a string and keeps on printing strings until infinity.

### Explanation:

```
.V0      for b in (0 to infinity):
    ^zb     compute all strings of length b consisting of the input alphabet
   j        print each one on a separate line

```

Alternatively the following will also work. A little bit more hacky though.

```
u
M^zH7

```
> 3 votes

# Answer
# MATL, 10 bytes

```
0cD`G@Z^DT

```

**Try it online!** But don't leave it running for long, to avoid large computational load on the server.

The program displays the strings dynamically, each string on a different line.

```
0cD             % force display of a newline to represent the empty string
   `      T     % infinite do-while loop
    G           % push input, or nothing if no input has been taken yet
     @          % push iteration. Gives 1, 2,... in each iteration
      Z^        % Cartesian power. In the first iteration takes input implicitly
       D        % display

```
> 3 votes

# Answer
# Haskell, 33 bytes

```
k u=do s<-[0..];mapM(\_->u)[1..s]

```

For exampe, `k "xyz"` is the infinite list `["","x","y","z","xx","xy","xz","yx","yy","yz","zx","zy","zz","xxx",...]`
> 3 votes

# Answer
# Husk, <sup>~~6 7~~</sup> 5 bytes

```
Θṁπ⁰N

```

Try it online!

## Explanation

```
 ṁ  N map natural numbers to:
  π⁰  cartesian power of input
 ṁ    and join
Θ     prepend empty string

```
> 3 votes

# Answer
## Ruby, ~~65~~ 60 bytes

```
->a{n=-1;loop{puts a.repeated_permutation(n+=1).map &:join}}

```

Such long builtin names...
> 2 votes

# Answer
# Python 3, 95

```
from itertools import*
def f(x,l=0):
 while 1:print(*combinations_with_replacement(x*l,l));l+=1

```

Why must itertools functions have such long names.
> 2 votes

# Answer
# Scala, 69

```
def f[A](s:Set[A]):Stream[List[A]]=Nil#::f(s).flatMap(x=>s.map(_::x))

```

Lazy streams are quite nice for this kind of thing.
> 2 votes

# Answer
# C (gcc), ~~99~~ ~~97~~ ~~95~~ 93 bytes

-2 bytes thanks to @ceilingcat (replaced `putchar(v[~s[i++]])` by `printf(v+~s[i++])`).

-2 more bytes thanks to @ceilingcat (made `i` a pointer rather than an index).

-2 bytes once more, again thanks to ceilingcat (replaced `(*i)--+l` by `--*i==~l`, reversing the last two arguments of the ternary conditional operator, making it possible to remove the parentheses around `*i++=-1`).

```
s[999];*i;f(v,l)int*v;{for(i=s;printf(v+~*i++););for(i=s,puts("");;)--*i==~l?*i++=-1:f(v,l);}

```

Try it online!
> 2 votes

# Answer
# Japt, ~~50~~ ~~40~~ ~~34~~ 28 bytes

```
V²o ®s1+Ul)£UgXnH)¯X¦0}Ãâ ¯V

```

Input is `"string", number of items`. Output is sorted by length, then reverse alphabet order. Test it online!

### How it works

```
V²  o ®   s1+Ul)£  UgXnH)¯  X¦ 0}Ã â ¯  V
Vp2 o mZ{Zs1+Ul)mX{UgXnH)s0,X!=0}} â s0,V

Vp2 o      // Create the range [0..V²).
mZ{     }  // Map each item Z in this range to:
Zs1+Ul)    //  Take the base-(1+U.length) representation of Z.
mX{     }  //  Map each char X in this to:
XnH        //   Parse X as a base-32 number.
Ug   )     //   Take the char at index -^ in U.
s0,X!=0    //   If X is 0, slice it to an empty string.
â          // Uniquify the result.
s0,V       // Slice to the first V items.

```

This version takes a while if you want to do any more than 100 items. If you want a faster version, try this 32-byte one:

```
V*2 o ms1+Ul)f@!Xf'0Ã®£UgXnH}Ã¯V

```
> 1 votes

# Answer
## Pyke (commit 31), ~~10~~ 9 bytes

```
=blR.fbtp

```

Explanation:

```
=b         -    set characters for base conversion to eval_or_not(input())
  l        -   len(^)
   R      -  [^, eval_or_not(input()]
    .f    - first_n(^)
      b   -    conv_base(^)
       t  -   ^[-1]
        p -  print(^)

```
> 1 votes

# Answer
# Cinnamon Gum, 6 bytes

```
0000000: 6801 301c e74b                           h.0..K

```

Non-competing because Cinnamon Gum was made after this challenge.

Try it online (TIO limits output).

## Explanation

The `h` puts Cinnamon Gum in *format and generate mode*. The rest of the string decompresses to `[%s]*`. The `%s` is then replaced with the input, and a generator is created that outputs all possible strings matching the regex.
> 1 votes

# Answer
# 05AB1E, 9 bytes

```
g<∞*εÅв¦J

```

Try it online!

```
g             # length of the input
 <            # - 1
  ∞           # infinite list [1, 2, 3, …]
   *          # multiply each by the length-1
    ε         # for each:
     Åв       #  custom base conversion, using the input as the list of digits
       ¦      #  chop off the first digit
        J     #  join the rest to a string

```
> 1 votes

# Answer
# , ~~53~~ 50 bytes

-3 bytes thanks to Dominic van Essen

```
r=scan(,s<-"");repeat cat("",s<-outer(s,r,paste0))

```

Try it online!

Prints the infinite list, separated by spaces.
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
∞€ã˜õš

```

Try it online!

```
∞        # push a list of all positive integers
 €ã      # take the input to each cartesian power
   ˜     # flatten the resulting list of lists
    õ    # push the empty string
     š   # prepend it to the infinite list of strings

```

Taking a string the 0th cartesian cartesian yields `[[]]`, which would get completely lost when flattening (`˜`), this is why the empty string is prepended manually.
`∞<€ã€`` is an alternative 6-byter which uses `[]` to represent the empty string.
> 1 votes

# Answer
# Curry (KiCS2), 18 bytes

```
f s=""?anyOf s:f s

```

Attempt This Online!
> 1 votes

# Answer
# Vyxal, 4 bytes

```
ƛ⁰τḢ

```

Try it Online! Takes the number of strings and the string.

```
ƛ    # For each number in 1...n
 ⁰τ  # Convert to base <string>
   Ḣ # Remove the first character

```

Alternatively, a version that prints infinitely (and is probably more efficient)

# Vyxal, 6 bytes

```
{:⁋,ẊṠ

```

Try it Online!

```
{      # Forever
 :⁋,   # Print the current string joined by newlines
    ẊṠ # Take the cartesian product with the input

```
> 1 votes

# Answer
## Python, 55 bytes

```
s=input();l=['']
for x in l:print x;l+=[x+c for c in s]

```

This is longer than feersum's 53-byte solution, but it illustrates a different method with printed output. The list `l` is updated while it is iterated over, by appending every one-character suffix of each string that is read.

It's equally long to use `map`:

```
s=input();l=['']
for x in l:print x;l+=map(x.__add__,s)

```

The same length can be done in Python 3, losing a char for `print()`, and saving one by input unpacking.

```
s,*l=input(),''
for x in l:print(x);l+=[x+c for c in s]

```
> 0 votes

# Answer
# Zsh, 31 bytes

```
f(){<<<${(F)a};a=($^a$^@);f $@}

```

Try it online!

Print the array, then zip on the arguments before recursing. Despite including the function name, this is one byte shorter than the iterative version:

```
for ((;;))<<<${(F)a}&&a=($^a$^@)

```
> 0 votes

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


title: Decimal Multiplication of Strings

text:
# Question
Title: Decimal Multiplication of Strings
Given two inputs, a string \\$s\\$ and a decimal number \\$n\\$, output the string multiplied by that number.

The catch is that the number can be a float or an integer.

You should output the string \\$\lfloor n \rfloor\\$ times and then the first \\$\lfloor (n - \lfloor n \rfloor) \cdot |\\,s\\,|)\rfloor\\$ characters again.

Other notes:

* The input will not always be a float, it may be an integer. So `1.5`, `1`, and `1.0` are all possible. It will always be in base 10 though, and if you wish an exception please comment.
* The string input may contain white space except newlines, quotes and other characters. Control characters are excluded, too, if this helps.
* No built-ins for direct string repetition are allowed. That means for instance Python’s `'a'*5` is forbidden. Nevertheless string concatenation (frequently denoted by the `+` sign) is allowed.

## Test cases

| \\$s\\$ | \\$n\\$ | result |
| --- | --- | --- |
| `test case` | `1` | `test case` |
| `case` | `2.5` | `casecaseca` |
| `(will add more later)` | `0.3333` | `(will` |
| `cats >= dogs` | `0.5` | `cats >` |

## Final Note

I am seeing a lot of answers that use builtin string multiplication or repetition functions. This is *not* allowed. The rule is: If it directly multiplies the string, you cannot do it.

# Answer
# Jelly, 5 bytes

```
×L}Rị

```

Doesn't use a repetition built-in. Try it online!

### How it works

```
×L}Rị  Main link. Left input: n (multiplier). Right input: S (string)

 L}    Yield the length of S.
×      Multiply it with n.
   R   Range; turn n×len(S) into [1, ... floor(n×len(S))].
    ị  Retrieve the elements of S at those indices.
       Indices are 1-based and modular in Jelly, so this begins with the first and
       jump back after reaching the last.

```
> 4 votes

# Answer
## Java 7, 89

```
void g(char[]a,float b){for(int i=0,l=a.length;i<(int)(l*b);)System.out.print(a[i++%l]);}

```

takes char\[\] and float and outputs to STDOUT. basic looping.
> 7 votes

# Answer
# JavaScript (ES6), 50 bytes

**Edit** 2 bytes more to include definition of function `f`. 1 byte less using the tip of @manatwork. Note: using `~` we have more iterations than necessary, but this is code golf and even 1 byte counts

```
f=(s,n,l=s.length*n)=>~n?f(s+s,n-1,l):s.slice(0,l)

```

**TEST**

```
f=(s,n,l=s.length*n)=>~n?f(s+s,n-1,l):s.slice(0,l)

//TEST
console.log=x=>O.textContent+=x+'\n'
;[
 ['test case', 1, 'test case'],
 ['case', 3.5, 'casecasecaseca'],
 ['(will add more later)', 0.3333, '(will '],
 ['cats >= dogs', 0.5, 'cats >']]
.forEach(t=>{
  var s=t[0],n=t[1],x=t[2],r=f(s,n);
  console.log("«"+s+"» "+n+' => «'+r+'» '+(x==r?'OK':'FAIL expected '+x));
 })
```

```
<pre id=O></pre>
```
> 6 votes

# Answer
# Pyth, ~~9~~ 8

```
s@Lz*lzQ

```

Saved 1 byte thanks to Pietu1998

This takes `floor(n * len(string))` letters from the string, using cyclical indexing. I believe this is always equivalent to the given formula.

Test Suite
> 6 votes

# Answer
# Vitsy, 9 bytes

Expects the word as an argument, and the number to multiply by through STDIN.

```
zlW*\[DO{]
z          Grab all string argument input.
 l         Get the length of the stack.
  W        Parse STDIN.
   *       Multiply the top two items (length of string and the number of repetitions)
    \[   ] Do the stuff in the loop.
      DO{  Output one char at a time, making sure to duplicate first.
```

Try it online!
> 4 votes

# Answer
## CJam, 10 bytes

```
l_,l~*,\f=

```

The string is supplied on the first line of STDIN, the float on the second.

Test it here.

### Explanation

```
l    e# Read string.
_,   e# Duplicate and get its length.
l~   e# Read second line and evaluate.
*    e# Multiply them. If the result, N, was floored it would give us the number of
     e# characters in the required output.
,    e# Get range [0 1 ... ⌊N⌋-1].
\f=  e# For each character in that range, fetch the corresponding character from the
     e# string using cyclic indexing.

```
> 3 votes

# Answer
# Python 2, 71 bytes

```
lambda s,x:"".join(s for i in range(int(x)))+s[:int(len(s)*(x-int(x)))]

```

Try it here!

Creates an unnamed lambda which takes the string as first argument and the float as second. Returns the repeated string.

This could be 46 if string repetition builtins were allowed :(
> 3 votes

# Answer
# Ruby, ~~49~~ 48 characters

```
->s,n{(0...(n*l=s.size).to_i).map{|i|s[i%l]}*''}

```

Sample run:

```
2.1.5 :001 > ->s,n{(0...(n*l=s.size).to_i).map{|i|s[i%l]}*''}['case', 2.5]
 => "casecaseca"

```
> 3 votes

# Answer
# Perl 6,  ~~46 41~~  39 bytes

```
{([~] $^a xx$^b)~$a.substr(0,$a.chars*($b%1))}    # 46 bytes
{substr ([~] $^a xx$^b+1),0,$a.chars*$^b}         # 41 bytes
{substr ([~] $^a xx$^b+1),0,$a.comb*$b}           # 39 bytes

```

Perl 6 has both a string repetition operator `x` and a list repetition operator `xx`.

Since the rules disallow string repetition, we repeat it as if it was a single element list instead. Then the list gets concatenated together, and a substring of it is returned.

### Usage:

```
# give it a lexical name
my &code = {substr ([~] $^a xx$^b+1),0,$a.chars*$^b}
#          {substr ($^a x$^b+1),0,$a.chars*$^b}

say code('test case', 1).perl;                  # "test case"
say code('case', 2.5).perl;                     # "casecaseca"
say code('(will add more later)', 0.3333).perl; # "(will "
say code('cats >= dogs', 0.5).perl;             # "cats >"

```
> 3 votes

# Answer
# osascript, 173 bytes

Oh my days, this is worse than I thought.

```
on run a
set x to a's item 1's characters
set y to a's item 2
set o to""
set i to 1
set z to x's items's number
repeat y*z
set o to o&x's item i
set i to i mod z+1
end
o
end
```

Returns the value of the string, another answer using cyclical indexing. Expects input as `"string" "repetitions"`.
> 2 votes

# Answer
## Haskell, 44 bytes

```
c x=x++c x
s#n=take(floor$n*sum[1|a<-s])$c s

```

Usage example: `"(will add more later)" # 0.3333` -\> `"(will "`.

How it works: `c` concatenates infinite copies of the string `x`. It behaves like the built-in `cycle`. `sum[1|a<-s]` is a custom length function that works with Haskell's strict type system as it returns a `Double` (the built-in `length` returns an `Int` which cannot be multiplied with `n`). `#` takes `floor (n * length(s))` characters from the cycled string `s`.
> 2 votes

# Answer
## PHP 5, ~~96~~ 87

9 bytes saved thanks to @manatwork

```
<?for($i=$z=0;$i++<floor(strlen($a=$argv[1])*$argv[2]);$z++)echo$a[$z]?:$a[$z=0];

```

Pretty straight forward looping answer.

### Ungolfed

```
<?
$a=$argv[1];
$z=0;
for($i=0; $i < floor(strlen($a)*$argv[2]); $i++) {
    // if the string offset is not set
    // then reset $z back to 0 so we can
    // echo the beginning of ths string again
    @$a[$z] ?: $z=0;
    echo $a[$z];
    $z++;
}

```
> 2 votes

# Answer
## Perl, 51 + 3 = 54 bytes

```
$l=<>*y///c;for$i(1..$l){push@a,/./g}say@a[0..$l-1]

```

Requires: `-n`, `-l` and `-M5.010` | `-E`:

```
 $ perl -nlE'$l=<>*y///c;for$i(1..$l){push@a,/./g}say@a[0..$l-1]' <<< $'test case\n1'
 test case
 $ perl -nlE'$l=<>*y///c;for$i(1..$l){push@a,/./g}say@a[0..$l-1]' <<< $'case\n2.5'
 casecaseca
 $ perl -nlE'$l=<>*y///c;for$i(1..$l){push@a,/./g}say@a[0..$l-1]' <<< $'(will add more later)\n0.3333'
 (will
 $ perl -nlE'$l=<>*y///c;for$i(1..$l){push@a,/./g}say@a[0..$l-1]' <<< $'cats >= dogs\n0.5'
 cats >

```

Explanation:

```
$l=<>*y///c;              # Calculate output length (eg. 2.5 * input length)
for$i(1..$l){push@a,/./g} # Push a lot of chars from input into @a
say@a[0..$l-1]            # Slice @a according to output length

```
> 2 votes

# Answer
# R, 59 bytes

```
function(s,l)cat(rawToChar(array(charToRaw(s),nchar(s)*l)))

```

As an unnamed function. This uses charToRaw to split the string into a vector of raws. This is filled into an array of length * l, converted back to char and output.
I was going to use strsplit, but it ended up being longer.

Test

```
> f=
+ function(s,l)cat(rawToChar(array(charToRaw(s),nchar(s)*l)))
> f('test case', 1) # -> test case
test case
> f('case', 2.5) # -> casecaseca
casecaseca
> f('(will add more later)', 0.3333) # -> (will(space)
(will
> f('cats >= dogs', 0.5) # -> cats >
cats >
>

```
> 2 votes

# Answer
# c (preprocessor macro), 71

```
j,l;
#define f(s,m) l=strlen(s);for(j=0;j<(int)(l*m);)putchar(s[j++%l])

```

Not much tricky here. Just need to make sure `l*m` is cast to an `int` before comparing to `j`.

Try it online.
> 1 votes

# Answer
# Oracle SQL 11.2, ~~154~~ 152 bytes

```
WITH v(s,i)AS(SELECT SUBSTR(:1,1,FLOOR(FLOOR((:2-FLOOR(:2))*LENGTH(:1)))),1 FROM DUAL UNION ALL SELECT :1||s,i+1 FROM v WHERE i<=:2)SELECT MAX(s)FROM v;

```

Un-golfed

```
WITH v(s,i) AS
(
  SELECT SUBSTR(:1,1,FLOOR(FLOOR((:2-FLOOR(:2))*LENGTH(:1)))),1 FROM DUAL
  UNION ALL
  SELECT :1||s,i+1 FROM v WHERE i<=:2
)
SELECT MAX(s) FROM v;

```

I went the recursive way, with the initialisation select taking care of the decimal part.

Saved 2 bytes thanks to @MickyT
> 1 votes

# Answer
## Seriously, 24 bytes

```
,╗,mi@≈╜n╜l(*≈r`╜E`MΣ)kΣ

```

Try it online!

Explanation:

```
,╗,mi@≈╜n╜l(*≈r`╜E`MΣ)kΣ
,╗                        get first input (string) and push it to register 0
  ,mi@≈                   get input 2 (x), push frac(x) (f), int(x) (n)
       ╜n                 push n copies of the string
         ╜l(*≈            push length of string, multiply by f, floor (substring length) (z)
              r`╜E`MΣ     push s[:z]
                     )kΣ  move fractional part of string to bottom, concat entire stack

```
> 1 votes

# Answer
## Pyth, 9 bytes

```
V*Elzp@zN

```

Basically just doing

```
             z = input()
V*Elz        for N in range(evaluatedInput()*len(z)):    # flooring is automatic
     p@zN        print(z[N], end="")                     # modular indexing

```
> 1 votes

# Answer
## Pascal, 138 B

This full `program` requires a processor compliant with ISO standard 10206 “Extended Pascal”. Trivial cases have been excluded: It is presumed that the input string `s` is *non-empty* and `n` is *positive*. NB: The golfed version caps `s` at a reasonable length of `999`.

```
program p(input,output);var s:string(999);n:real;begin
read(s,n);while n>1 do begin n:=n-1;write(s)end;write(s[1..trunc(length(s)*n)])end.

```

Ungolfed:

```
program decimalMultiplicationOfStrings(input, output);
    var
        { `string` is a schema data type defined by Extended Pascal.
          The `string(maxInt)` discriminates the schema data type.
          Henceforth the specific `string` has a capacity of `maxInt`. }
        s: string(maxInt);
        n: real;
    begin
        { You can specify `real` as well as `integer` literals for `n`.
          An `integer` value is automatically promoted to `real`. }
        read(s, n);
        { The `string` subrange notation used below in the last line
          may not specify an empty range (e. g. `1‥0` is illegal).
          Therefore the `while` loop’s condition is `n > 1`.
          If `n = 1`, the one copy is printed via the final line. }
        while n > 1 do
        begin
            n ≔ n − 1;
            write(s);
        end;
        { The subrange notation is defined by Extended Pascal.
          It cannot be used for strings that are `bindable`. }
        write(s[1‥trunc(length(s) * n)]);
    end.

```

Input is end-of-line separated. `s` can otherwise contain any character from `chr(0)` to (the implementation-defined) `maxChar` range.
> 0 votes

# Answer
# Nim, 75 bytes

```
func r[S,F](s:S,n:F):S=
 for i in 0..<int n*s.len.float:result&=s[i%%s.len]

```

Attempt This Online!
> 0 votes

# Answer
# Scala, 68 bytes

Golfed version. Try it online!

```
(s,n)=>{val l=s.length;(0 to (n*l).toInt-1).map(i=>s(i%l)).mkString}

```

Ungolfed version. Try it online!

```
object Main {
  def repeatString(s: String, n: Double): String = {
    val len = s.length
    val repeatLen = (n * len).toInt
    (0 until repeatLen).map(i => s(i % len)).mkString
  }

  def main(args: Array[String]): Unit = {
    println(repeatString("case", 2.5))
  }
}

```
> 0 votes

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


title: What's my score?

text:
# Question
Title: What's my score?
The question score on Stack Exchange is the total number of upvotes minus the total number of downvotes a question receives. However, the reputation gained/lost for every upvote/downvote is different (eg. 10/-2 on Code Golf).

Given the total reputation earned, the reputation gained by an upvote and the reputation lost by a downvote, list out all possible scores (unweighted, +1/-1 for upvote/downvote) the question could have).

## Rules

* The total reputation and the reputation per vote must be integers
* The upvote-reputation will be positive and the downvote-reputation will be negative
* Impossible question scores are not valid inputs
* You can output the possible question scores as an infinite list or generator, print each individually, etc.
* This is , so the shortest answer wins

## Examples

```
[total reputation, upvote-reputation, downvote-reputation] -> [question scores]

[28, 10, -2]  -> [2, -2, -6, -10, ...]
[34, 10, -2]  -> [1, -3, -7, -11, ...]
[11, 7, -5]   -> [1, -1, -3, -5, ...]
[82, 31, -11] -> [2, -18, -38, -58, ...]
[15, 5, -10]  -> [3, 4, 5, 6, ...]
[-38, 4, -9]  -> [-2, 3, 8, 13, ...]

```

# Answer
> 7 votes
# Python, 92 bytes

*-2 bytes, thanks to UndoneStudios*
*-7 bytes, thanks to SuperStormer*

```
lambda s,u,d:(a-b*2for a in count()for b in range(a)if(a-b)*u+b*d==s)
from itertools import*

```

Attempt This Online!

*outputs a generator*

**99 bytes without using `itertools`**:

```
lambda s,u,d:(a-b*2for a in N()for b in range(a)if(a-b)*u+b*d==s)
def N(i=0):
 while 1:yield i;i+=1

```

Attempt This Online!

## Explanation

Goes through all pairs `(x,y)` of non-negative integers and checks if `x` upvotes and `y` downvotes gives the right score

---

# Python, 115 bytes

```
def f(s,u,d):
 i=s<0;g=math.gcd(u,d);a=s*pow(d//g,-1,u//g)%u/g
 while 1:yield(s-d*a)/u-a-i*(u+d)/g;i+=1
import math

```

Attempt This Online!

*Direct solution, sadly longer than brute force*

*`from math import*` is not possible, as it will overwrite `pow`*

## Explanation

1. Solve `b*u+a*d=s` by using `s=a*d mod u` -\> `a=d⁻¹*s mod u` (dividing out the gcd of u and d to ensure inverting d is possible)
2. compute `b` from `a`
3. The possible scores are `(b-a)+k*gcd(u,d)` for an integer `k`

# Answer
> 6 votes
# 05AB1E, ~~17~~ ~~14~~ 12 bytes

-5 bytes (and even slower than before ) thanks to *@CommandMaster*.

```
∞Óʒ¹*OQ}ε2£Æ

```

Two separated inputs \\$\[upvoteRep,downvoteRep\]\\$ and \\$totalRep\\$.
Outputs an infinite list that includes duplicated items.

Try it online. (Extremely slow brute-force that barely outputs the first two unique terms of the example test case, so no test suite with all test cases.)

We can prevent the duplicated items for +2 bytes by adding a trailing :
Try it online.

**Earlier 14 bytes answer (partially also by *@CommandMaster*) that's a lot faster:**

```
∞Ý€ã€`ʒ¹*OQ}€Æ

```

Similar I/O as above.

Try it online.

We can prevent the duplicated items for +1 byte this time by adding a trailing `Ù`:
Try it online or verify the first five values of all test cases.

**Explanation:**

```
∞        # Push an infinite list of positive integers: [1,2,3,...]
 Ó       # Convert each to a list of exponents of its prime factorization:
         #  [[],[1],[0,1],[2],[0,0,1],[1,1],[0,0,0,1],[3],[0,2],[1,0,1],...]
ʒ¹*OQ}   # Only keep all valid lists for the given inputs:
ʒ    }   #  Filter this infinite list of lists by:
 ¹*      #   Multiply the first two values in the list by the first input-pair of
         #   [pos,neg] (or if it's a singleton list, multiply its value by just `pos`)
   O     #   Sum this pair (or singleton)
    Q    #   Check whether it's equal to the second (implicit) input-integer
ε2£Æ     # Calculate the question-scores of the remaining valid lists:
ε        #  Map over each remaining list in the infinite list:
 2£      #   Only keep (up to) the first 2 values
   Æ     #    Reduce it by subtracting: [a,b]→a-b or [a]→a
    }Ù   # (optional) Close the map, and uniquify this infinite list of values
         # (after which the infinite list of scores is output implicitly as result)

```

```
∞Ý€ã€`   # Generate an infinite list of non-negative pairs:
∞        #  Push an infinite list of positive integers: [1,2,3,...]
 Ý       #  Convert each value to a [0,v]-ranged list: [[0,1],[0,1,2],[0,1,2,3],...]
  €ã     #  Map over each list, and get its cartesian power of 2 to create pairs:
         #   [[[0,0],[0,1],[1,0],[1,1]],[[0,0],[0,1],[0,2],[1,0],...],...]
    €`   #  Flatten the list of lists of pairs one level down:
         #   [[1,1],[1,0],[0,1],[0,0],[2,2],[2,1],[2,0],[1,2],[1,1],[1,0],...]
ʒ¹*OQ}   # Only keep all valid pairs for the given inputs:
ʒ    }   #  Filter this infinite list of pairs by:
 ¹*      #   Multiply the values in the pair by the first input-pair of [pos,neg]
   O     #   Sum the values in this pair together
    Q    #   Check whether it's equal to the second (implicit) input-integer
€Æ       # Calculate the question-scores of the remaining valid pairs:
€        #  Map over each remaining pair in the infinite list:
 Æ       #   Reduce the pair by subtracting: [a,b]→a-b
  Ù      # (optional) Uniquify this infinite list of values
         # (after which the infinite list of scores is output implicitly as result)

```

# Answer
> 5 votes
# Ruby, ~~60~~ 49 bytes

```
->r,u,d{0.step{|a|q=r-d*a;q%u<1&&q>-u&&p(q/u-a)}}

```

Try it online!

For any number of downvotes, check if the difference between the score and the sum of downvotes can be divided by the upvote score.

# Answer
> 5 votes
# Rust, ~~127~~ ~~123~~ 93 bytes

Port of @G B's Ruby anwser in Rust.

Saved 30 bytes thanks to the comment of @c--

---

Golfed version. Try it online!

```
|r,u,d|(|mut a,mut b|loop{if a*u+b*d==r{print!("{}
",a-b)}if a*u+b*d>r{b+=1}else{a+=1}})(0,0)

```

Ungolfed version. Try it online!

```
fn find_pairs(r: i32, u: i32, d: i32) {
    let mut a = 0;
    let mut b = 0;

    loop {
        let z = a * u + b * d;

        if z > r {
            b += 1;
        } else if z == r {
            println!("{}", a - b);
            a += 1;
        } else {
            a += 1;
        }
    }
}

fn main() {
    find_pairs(28, 10, -2);
}

```

# Answer
> 5 votes
# Python 3,  ~~72 67 66 65 57~~  55 bytes

-6 thanks to xnor! (Inlining the while loop by use of `(yield ...)` being `None`, in turn allowing for post-incrementing. Suggesting printing.)
-7 more thanks to xnor! (Refactor to a recursive function.)
-2 thanks to Neil (Since `d` is guaranteed to be negative `0<=r/d` may be replaced with `0>=r`).

```
def f(r,u,d,p=0):r%d==0>=r!=print(p-r/d);f(r-u,u,d,p+1)

```

A function that accepts the reputation, `r`, the upvote delta, `u` and the downvote delta, `d`, and prints the potential scores forever.

**Try it online!** (Harnessed to halt printing early.)

### How?

`p` is the upvote count and is initialised to `0` for the first call in the function's parameters (`,p=0`). Subsequent calls (`f(r-u,u,d,p+1)`) are each for one more upvote (`p+1`) and for the outstanding reputation (`r-u`).

Each call evaluates whether any non-negative (`0>=r`) integer number of downvotes is valid (`r%d==0`) and prints the upvotes less the downvotes (`print(p-r/d)`) if so (when `!=` is reached causing evaluation).

# Answer
> 4 votes
# Charcoal, 44 bytes

```
ＮθＮηＮζ≦⁻×⁺ηζ∧›θ⁰±÷θ±ηθＷ¹«Ｆ¬﹪θζ«Ｉ÷θζＤ⎚»≧⁺⁺ηζθ

```

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

```
ＮθＮηＮζ

```

Input the question, upvote and downvote reputations.

```
≦⁻×⁺ηζ∧›θ⁰±÷θ±ηθ

```

If the question reputation is positive, adjust it for the minimum number of upvotes required. If it is negative, just negate it.

```
Ｗ¹«

```

Repeat indefinitely.

```
Ｆ¬﹪θζ«Ｉ÷θζＤ⎚»

```

If the question reputation is a multiple of the downvote reputation then output the possible score.

```
≧⁺⁺ηζθ

```

Add both the upvote and downvote reputations to the question reputation. This allows the score to be determined solely from the downvote reputation.

Note that the behaviour on TIO is for `Dump` to pause 10ms since the last `Dump`, meaning that the script usually times out after printing 6000 possible scores. The newer version of Charcoal on ATO supports the `--nt` option which disables this pause, allowing it to fill the 128KB output buffer instead. Attempt This Online! Link is to verbose version of code.

---
Tags: code-golf, math, array
---