title: Bernoulli Numbers

text:
# Question
Title: Bernoulli Numbers
The Bernoulli numbers (specifically, the second Bernoulli numbers) are defined by the following recursive definition:

Where  denotes a combination.

Given a nonnegative integer `m` as input, output the decimal representation OR a reduced fraction for the `m`th second Bernoulli number. If you output a decimal representation, you must have at least 6 decimal places (digits after the decimal point) of precision, and it must be accurate when rounded to 6 decimal places. For example, for `m = 2`, `0.166666523` is acceptable because it rounds to `0.166667`. `0.166666389` is not acceptable, because it rounds to `0.166666`. Trailing zeroes may be omitted. Scientific notation may be used for decimal representations.

Here is the input and expected output for `m` up to and including 60, in scientific notation rounded to 6 decimal places, and as reduced fractions:

```
0 -> 1.000000e+00 (1/1)
1 -> 5.000000e-01 (1/2)
2 -> 1.666667e-01 (1/6)
3 -> 0.000000e+00 (0/1)
4 -> -3.333333e-02 (-1/30)
5 -> 0.000000e+00 (0/1)
6 -> 2.380952e-02 (1/42)
7 -> 0.000000e+00 (0/1)
8 -> -3.333333e-02 (-1/30)
9 -> 0.000000e+00 (0/1)
10 -> 7.575758e-02 (5/66)
11 -> 0.000000e+00 (0/1)
12 -> -2.531136e-01 (-691/2730)
13 -> 0.000000e+00 (0/1)
14 -> 1.166667e+00 (7/6)
15 -> 0.000000e+00 (0/1)
16 -> -7.092157e+00 (-3617/510)
17 -> 0.000000e+00 (0/1)
18 -> 5.497118e+01 (43867/798)
19 -> 0.000000e+00 (0/1)
20 -> -5.291242e+02 (-174611/330)
21 -> 0.000000e+00 (0/1)
22 -> 6.192123e+03 (854513/138)
23 -> 0.000000e+00 (0/1)
24 -> -8.658025e+04 (-236364091/2730)
25 -> 0.000000e+00 (0/1)
26 -> 1.425517e+06 (8553103/6)
27 -> 0.000000e+00 (0/1)
28 -> -2.729823e+07 (-23749461029/870)
29 -> 0.000000e+00 (0/1)
30 -> 6.015809e+08 (8615841276005/14322)
31 -> 0.000000e+00 (0/1)
32 -> -1.511632e+10 (-7709321041217/510)
33 -> 0.000000e+00 (0/1)
34 -> 4.296146e+11 (2577687858367/6)
35 -> 0.000000e+00 (0/1)
36 -> -1.371166e+13 (-26315271553053477373/1919190)
37 -> 0.000000e+00 (0/1)
38 -> 4.883323e+14 (2929993913841559/6)
39 -> 0.000000e+00 (0/1)
40 -> -1.929658e+16 (-261082718496449122051/13530)
41 -> 0.000000e+00 (0/1)
42 -> 8.416930e+17 (1520097643918070802691/1806)
43 -> 0.000000e+00 (0/1)
44 -> -4.033807e+19 (-27833269579301024235023/690)
45 -> 0.000000e+00 (0/1)
46 -> 2.115075e+21 (596451111593912163277961/282)
47 -> 0.000000e+00 (0/1)
48 -> -1.208663e+23 (-5609403368997817686249127547/46410)
49 -> 0.000000e+00 (0/1)
50 -> 7.500867e+24 (495057205241079648212477525/66)
51 -> 0.000000e+00 (0/1)
52 -> -5.038778e+26 (-801165718135489957347924991853/1590)
53 -> 0.000000e+00 (0/1)
54 -> 3.652878e+28 (29149963634884862421418123812691/798)
55 -> 0.000000e+00 (0/1)
56 -> -2.849877e+30 (-2479392929313226753685415739663229/870)
57 -> 0.000000e+00 (0/1)
58 -> 2.386543e+32 (84483613348880041862046775994036021/354)
59 -> 0.000000e+00 (0/1)
60 -> -2.139995e+34 (-1215233140483755572040304994079820246041491/56786730)

```

Reference implementation (in Python 3):

```
def factorial(n):
    if n < 1:
        return 1
    else:
        return n * factorial(n - 1)

def combination(m,k):
    if k <= m:
        return factorial(m)/(factorial(k) * factorial(m - k))
    else:
        return 0

def Bernoulli(m):
    if m == 0:
        return 1
    else:
        t = 0
        for k in range(0, m):
            t += combination(m, k) * Bernoulli(k) / (m - k + 1)
        return 1 - t

```

### Rules

* This is , so shortest code in bytes wins
* You may not use any functions, either built-in or included in an external library, that compute either type of Bernoulli numbers or Bernoulli polynomials.
* Your answer must give correct output for all inputs up to and including 60.

# Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard 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

```

```
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><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="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{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><script>var QUESTION_ID = 65382; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
```

# Answer
# Julia, ~~23~~ 20 bytes

Saved 3 bytes thanks to Alex A.

It uses the same formula as my Mathematica solution and PARI/GP solution.

```
n->n>0?-zeta(1-n)n:1

```
> 7 votes

# Answer
# Mathematica, ~~40~~ ~~28~~ ~~23~~ 22 bytes

Using the famous formula *n***ζ*(1−*n*)=−*B**n*, where *ζ* is the Riemann Zeta function.

```
If[#>0,-Zeta[1-#]#,1]&

```

The same length:

```
B@0=1;B@n_=-Zeta[1-n]n

```

---

Original solution, 40 bytes, using the generating function of Bernoulli numbers.

```
#!SeriesCoefficient[t/(1-E^-t),{t,0,#}]&

```
> 25 votes

# Answer
# Julia, 58 bytes

```
B(m)=m<1?1:1-sum(k->big(binomial(m,k))*B(k)/(m-k+1),0:m-1)

```

This creates a recursive function `B` that accepts an integer and returns a `BigFloat` (i.e. high precision floating point).

Ungolfed:

```
function B(m::Integer)
    m == 0 && return 1
    return 1 - sum(k -> big(binomial(m, k)) * B(k) / (m-k+1), 0:m-1)
end

```
> 8 votes

# Answer
## Minkolang 0.14, 97 bytes

I actually tried doing it recursively first, but my interpreter, as currently designed, actually can't do it. If you try to recurse from within a for loop, it starts a new recursion. So I went for the tabulating approach...which had precision problems. So I did the whole thing with fractions. With no built-in support for fractions. \[*sigh*\]

```
n1+[xxi$z0z2%1+F0c0=$1&$d4Mdm:1R:r$dz1Az0A]$:N.
11z[i0azi6M*i1azi-1+*d0c*1c2c*-1c3c*4$X]f
z1=d1+f

```

Try it here. Bonus: the array has all fractions for every previous Bernoulli number!

### Explanation (in a bit)

```
n1+                 Take number from input (N) and add 1
   [                Open for loop that runs N+1 times (starts at zero)
    xx              Dump the top two values of the stack
      i$z           Store the loop counter in the register (m)
         0          Push 0
          z2%1+     Push 1 if N is even, 2 if odd
               F    Gosub; pops y,x then goes to codebox(x,y), to be returned to

    0c                                 Copy the first item on the stack
      ,                                1 if equal to 0, 0 otherwise
       $1&                             Jump 11 spaces if top of stack is not 0

                                       (If top of stack is not 0, then...)
          $d                           Duplicate whole stack
            4M                         Pop b,a and push GCD(a,b)
              dm                       Duplicate and merge (a,b,c,c -> a,c,b,c)
                :                      Divide
                 1R                    Rotate 1 item to the right (0G works too)
                   :                   Divide
                    r                  Reverse stack

                                       (In both cases...)
                     $d                Duplicate whole stack
                       z1A             Store denominator of B_m in array
                           z0A         Store numerator of B_m in array
                              ]        Close for loop
                               $:      Divide (float division)
                                 N.    Output as number and stop.

11                                           Push two 1s (a, b)
  z[                                         Open a for loop that repeats m times
    i0a                                      Retrieve numerator of B_k (p)
       zi                                    Push m, k
         6M                                  Pop k,m and push mCk (binomial) (x)
           *                                 p*x (c)
            i1a                              Retrieve denominator of B_k (q)
               zi-1+                         m-k+1 (y)
                    *                        q*y (d)
                     d                       Duplicate top of stack
                      0c*                    a*d
                         1c2c*               b*c
                              -              a*d-b*c
                               1c3c*         b*d
                                    4$X      Dump the bottom four items of stack
                                       ]f    Jump back to F

z          m
 1=        0 (if m is 1) or 1 (otherwise)
   d1+     Duplicate and add 1 (1 or 2)
      f    Jump back to F

```

The third line is responsible for `1/2` if `m` is 1 and `0/1` if `m` is an odd number greater than 1. The second line calculates `B_m` with the summation formula given in the question, and does so entirely with numerators and denominators. Otherwise it'd be a lot shorter. The first half of the first line does some bookkeeping and chooses whether to execute the second or third line, and the second half divides the numerator and denominator by their GCD (if applicable) and stores those values. And outputs the answer at the end.
> 8 votes

# Answer
# Python 2, 118 bytes

*Saved 6 bytes due to xsot.*
*Saved ~~6~~ 10 more due to Peter Taylor.*

```
n=input()
a=[n%4-1,n<2]*n;exec"a=[(a[j-1]+a[j+1])*j/2for j in range(len(a)-2)];"*~-n
print+(n<1)or-n/(2.**n-4**n)*a[1]

```

Uses the following identity:

where *An* is the *nth* Alternating Number, which can be formally defined as the number of alternating permutations on a set of size *n*, halved (see also: A000111).

The algorithm used was originally given by Knuth and Buckholtz (1967):

> *Let T1,k = 1 for all k = 1..n*
>
> *Subsequent values of T are given by the recurrence relation:*
>
> *Tn+1,k = 1/2* \[ *(k - 1) Tn,k-1 \+ (k + 1) Tn,k+1* \]
>
> *An is then given by Tn,1*
>
> (see also: A185414)

---

## Python 2, 152 bytes

```
from fractions import*
n=input()
a=[n%4-1,n<2]*n
for k in range(n-1):a=[(a[j-1]+a[j+1])*j/2for j in range(n-k)]
print+(n<1)or Fraction(n*a[1],4**n-2**n)

```

Prints the exact fractional representation, necessary for values greater than 200 or so.
> 7 votes

# Answer
# Python 3, 112 bytes

**Edit:** I cleaned up this answer. If you want to see all the other ways I thought of to answer this question in Python 2 and 3, look in the revisions.

If I don't use the lookup table (and I use memoization instead), I manage to get the recursive definition to 112 bytes! WOO! Note that `b(m)` returns a `Fraction`. As usual, the byte count and a link for testing.

```
from fractions import*
def b(m):
 s=k=0;p=1
 while k<m:a=m-k;s+=Fraction(p*b(k))/-~a;p=p*a//-~k;k+=1
 return 1-s

```

And a function that does use a lookup table, and returns the whole table of fractions from `b(0)` to `b(m)`, inclusive.

```
from fractions import*
def b(m,r=[]):
 s=k=0;p=1
 while k<m:
  if k>=len(r):r=b(k,r)
  a=m-k;s+=Fraction(p*r[k])/-~a;p=p*a//-~k;k+=1
 return r+[1-s]

```
> 5 votes

# Answer
# PARI/GP, ~~52~~ 23 bytes

Using the famous formula *n***ζ*(1−*n*)=−*B**n*, where *ζ* is the Riemann Zeta function.

```
n->if(n,-n*zeta(1-n),1)

```

---

Original solution, 52 bytes, using the generating function of Bernoulli numbers.

```
n->n!*polcoeff(-x/sum(i=1,n+1,(-x)^i/i!)+O(x^n*x),n)

```
> 5 votes

# Answer
## CJam, ~~69 49 34~~ 33 bytes

```
{_),:):R_:*_@f/@{_(;.-R.*}*0=\d/}

```

Online demo

Thanks to Cabbie407, whose answer made me aware of the Akiyama–Tanigawa algorithm.

### Dissection

```
{           e# Function: takes n on the stack
  _),:)     e# Stack: n [1 2 3 ... n+1]
  :R        e# Store that array in R
  _:*       e# Stack: n [1 2 3 ... n+1] (n+1)!
  _@f/      e# Stack: n (n+1)! [(n+1)!/1 (n+1)!/2 (n+1)!/3 ... (n+1)!/(n+1)]
            e#   representing [1/1 1/2 ... 1/(n+1)] but avoiding floating point
  @{        e# Repeat n times:
    _(;.-   e#   Take pairwise differences
    R.*     e#   Pointwise multiply by 1-based indices
  }*        e#   Note that the tail of the array accumulates junk, but we don't care
  0=\d/     e# Take the first element and divide by (n+1)!
}

```
> 5 votes

# Answer
## Mathematica, ~~52~~ ~~48~~ 42 bytes

```
1-Sum[#~Binomial~k#0@k/(#-k+1),{k,0,#-1}]&

```

Unnamed function that uses the literal definition.
> 3 votes

# Answer
# PARI/GP, 45 bytes

```
n->if(n,2*n/(2^n-4^n)*real(polylog(1-n,I)),1)

```

Using the same formula as my Python answer, with *An* generated via polylog.

---

**Test Script**

Run `gp`, at the prompt paste the following:

```
n->if(n,2*n/(2^n-4^n)*real(polylog(1-n,I)),1)
for(i=0, 60, print(i, ": ", %(i)))

```
> 3 votes

# Answer
# Python 2, ~~132~~ 130 bytes

```
import math,fractions
f=math.factorial
B=lambda m:~-m*m%2or 1+sum(B(k)*f(m)/f(k)/f(m-k)/fractions.Fraction(k+~m)for k in range(m))

```

This is just a golfed version of the reference implementation.

This is a little slow in practice, but can be sped up significantly with memoization:

```
import math,fractions
f=math.factorial

def memoize(f):
 memo = {}
 def helper(x):
  if x not in memo:
   memo[x] = f(x)
  return memo[x]
 return helper

@memoize
def B(m):
 return~-m*m%2or 1+sum(B(k)*f(m)/f(k)/f(m-k)/fractions.Fraction(k+~m)for k in range(m))

for m in range(61):
 print(B(m))

```

You can try this version online on Ideone.
> 2 votes

# Answer
# gawk4, 79 bytes

77 bytes code + 2 bytes for `-M` flag

```
PREC^=2{for(n=$0;m++<=n;)for($(j=m)=1/m;j>1;)$j=(-$j+$--j)*j;printf"%.6f",$1}

```

It's an implementation of the Akiyama–Tanigawa algorithm from the Wikipedia page.

Had some trouble with the "6-decimal-digits-rule", because this prints the whole number and then 6 digits, but there is no list here to compare the results.

A flaw is that this prints a minus sign in front of the `0.000000` al lot of times, but I don't think that's wrong.

## Usage example

```
echo 58 | awk -M 'PREC^=2{for(n=$0;m++<=n;)for($(j=m)=1/m;j>1;)$j=(-$j+$--j)*j;printf"%.6f",$1}'

```

## Output from 0 to 60

```
0 -> 1.000000
1 -> 0.500000
2 -> 0.166667
3 -> -0.000000
4 -> -0.033333
5 -> 0.000000
6 -> 0.023810
7 -> 0.000000
8 -> -0.033333
9 -> 0.000000
10 -> 0.075758
11 -> -0.000000
12 -> -0.253114
13 -> -0.000000
14 -> 1.166667
15 -> -0.000000
16 -> -7.092157
17 -> -0.000000
18 -> 54.971178
19 -> -0.000000
20 -> -529.124242
21 -> -0.000000
22 -> 6192.123188
23 -> 0.000000
24 -> -86580.253114
25 -> 0.000000
26 -> 1425517.166667
27 -> 0.000000
28 -> -27298231.067816
29 -> 0.000000
30 -> 601580873.900642
31 -> 0.000000
32 -> -15116315767.092157
33 -> 0.000000
34 -> 429614643061.166667
35 -> 0.000000
36 -> -13711655205088.332772
37 -> 0.000000
38 -> 488332318973593.166667
39 -> -0.000000
40 -> -19296579341940068.148633
41 -> -0.000000
42 -> 841693047573682615.000554
43 -> -0.000000
44 -> -40338071854059455413.076812
45 -> -0.000000
46 -> 2115074863808199160560.145390
47 -> -0.000000
48 -> -120866265222965259346027.311937
49 -> -0.000000
50 -> 7500866746076964366855720.075758
51 -> -0.000000
52 -> -503877810148106891413789303.052201
53 -> -0.000000
54 -> 36528776484818123335110430842.971178
55 -> -0.000000
56 -> -2849876930245088222626914643291.067816
57 -> -0.000000
58 -> 238654274996836276446459819192192.149718
59 -> -0.000000
60 -> -21399949257225333665810744765191097.392674

```
> 2 votes

# Answer
# R, 93 bytes

```
function(m){if(m==0){1}else{v=c();for(k in 0:(m-1))v=c(v,choose(m,k)*f(k)/(m-k+1));1-sum(v)}}

```

Not really original as a solution. If any comment, please feel free !

**Ungolfed :**

```
function(m)
    if(m==0){1}
    else
         v=c()
         for(k in 0:(m-1))
            v=c(v,choose(m,k)*f(k)/(m-k+1))

1-sum(v)

```
> 2 votes

# Answer
# GolfScript, 63 bytes

```
~:i.!+.[3i&(2i>]*i(,{i\-,{1$1$(=2$2$)=+*2/}%\;}/~\2i?.(*\--1?**

```

Online Demo.

Using the same formula as my Python answer.

---

**Test Script**

```
61,{[.`
  ~:i.!+.[3i&(2i>]*i(,{i\-,{1$1$(=2$2$)=+*2/}%\;}/~\2i?.(*\--1?**
]p}/

```

The apphb link will time out on this. If you don't have GolfScript installed locally, I recommend using the anarchy golf interpreter (use form, select GolfScript, paste, submit).
> 1 votes

# Answer
# Perl, 101 bytes

```
#!perl -p
@a=($_%4-1,$_<2)x$_;
@a=map$_*($a[$_-1]+$a[$_+1])/2,0..@a-3for 2..$_;
$_=!$_||$_/(4**$_-2**$_)*$a[1]

```

Counting the shebang as three, input is taken from stdin.

Using the same formula as my Python answer.

---

**Sample Usage**

```
$ echo 60 | perl bernoulli.pl
-2.13999492572253e+034

```

Online Demo.
> 1 votes

# Answer
# Ruby, ~~66~~ 61 bytes

This is a Ruby version of my Python answer.

```
b=->m{s,p=0r,1;m.times{|k|a=m-k;s+=p*b[k]/-~a;p=p*a/-~k};1-s}

```

Since this uses `Rational` in its answers, I'm fairly sure this works up to 60, but I had trouble running even `b[24]`, so I implemented the lookup table again for ~~86~~ ~~81~~ 80 bytes.

```
t=->m{s,p,r=0r,1,m>0?t[m-1]:[];m.times{|k|a=m-k;s+=p*r[k]/-~a;p=p*a/-~k};r<<1-s}

```
> 1 votes

# Answer
# Actually, ~~46~~ 45 bytes

I've been meaning to do a Seriously/Actually answer for months and now I can. Golfing suggestions welcome. Try it online!

**Edit:** In February of 2017, there was an update to Actually that changed which function literals are which. Enjoy.

This uses the explicit definition of the Bernoulli numbers on Wikipedia.

```
;╖ur⌠;╝ur⌠;;0~ⁿ(╛█*╜(uⁿ*⌡MΣ╛uk⌡M┬i@;π;)♀\*@k▼

```

**Ungolfing**

```
;╖     Duplicate and save m in register 0.
ur     Range [0..m]
  ⌠      Start first for loop
  ;╝     Duplicate and save k in register 1.
  ur     Range [0..k]
    ⌠      Start second for loop (as string).
    ;;     Duplicate v twice.
    0~ⁿ    Push -1, and pow() to get (-1)**v.
    (╛█    Rotate a duplicate v to TOS, push k, and binom(k, v).
    *      Multiply (-1)**v by binom(k, v).
    ╜(uⁿ   Push m, rotate last duplicate v to TOS, increment, and pow() to get (v+1)**m.
    *      (-1)**v * binom(k, v) * (v+1)**m
    ⌡      End second for loop (string turned to function).
  MΣ     Map over range [0..v] and sum
  ╛u     Push k and increment (the denominator)
           (Note: second for loop does numerators only as denominator only depends on k)
  k      Push fraction in list form [numerator, denominator]
  ⌡      End first for loop
M      Map over range [0..k]
┬i@    Transpose all of the fractions, flatten and swap.
         Stack: [denominators] [numerators]
;π     Duplicate and take product of denominators.
;)     Duplicate product and move to bottom of stack.
         Stack: product [denominators] [numerators] product
♀\     For all items in denominators, integer divide product by item.
         Return a list of these scaled-up denominators.
*      Dot product of numerators and the scaled-up denominators as new numerator.
         (In effect, getting the fractions to the same denominator and summing them)
@k     Swap new numerator and product (new denominator) and turn into a list (fraction).
▼      Divide fraction by gcd(numerator, denominator) (Simplify fraction).

```
> 1 votes

# Answer
# J, 10 bytes

```
(%1-^@-)t:

```

Computes the *nth* Bernoulli number by finding the *nth* coefficient of the exponential generating function of *x*/(1 - *e-x*).

## Usage

If the input is given integer or floats as an argument, it will output a float. If given an extended integer, marked with a suffix `x`, it will output either an extended integer or a rational, two extended integers separated by `r`.

```
   f =: (%1-^@-)t:
   f 1
0.5
   f 1x
1r2
   (,.f"0) i. 10x
0     1
1   1r2
2   1r6
3     0
4 _1r30
5     0
6  1r42
7     0
8 _1r30
9     0

```

## Explanation

```
(%1-^@-)t: Input: n
(      )t: Takes a monad and creates a new monad that
           computes the coefficients of its egf
(      )   A monad that operates on x
      -      Negate x
    ^@       Computes its exponential, e^-x
  1-         Subtract it from 1
 %           Divide x by it, x/(1 - e^-x)

```
> 1 votes

# Answer
# Axiom, ~~134~~ 147 bytes

```
b(n:NNI):FRAC INT==(v:=[1/1];k:=1;repeat(k>n=>break;r:=1-reduce(+,[binomial(k,j)*v.(j+1)/(k-j+1)for j in 0..k-1]);v:=append(v,[r]);k:=k+1);v.(n+1))

```

ungolf and test

```
(23) -> b
   (23)
   b n ==
           1
     v := [-]
           1
     k := 1
     repeat
       if n < k
         then break
         else
                               binomial(k,j)v(j + 1)
           r := 1 - reduce(+,[[--------------------- for j in 0..(k - 1)]])
                                     k - j + 1
           v := append(v,[r])
           k := k + 1
     v(n + 1)
                                                   Type: FunctionCalled b
(50) -> [[i,b(i)]  for i in [0,1,2,3,4,5,6,7,8,9,10]]
   (50)
             1     1              1            1              1             5
   [[0,1],[1,-],[2,-],[3,0],[4,- --],[5,0],[6,--],[7,0],[8,- --],[9,0],[10,--]]
             2     6             30           42             30            66
                                         Type: List List Fraction Integer

(51) -> b 1000
   (51)
   -
   18243104738661887254572640256857788879338336867042906052197158157641126_
    2572624911158657472577321069709615489924627495522908087488299539455188_
    7918567582241551668492697244184914012242579830955617098629924652251740_
    9791915637226361428342780548971002281045465308441161372350696920220116_
    2441791760680262602019620260255790058416539271332852806000966628467639_
    0683434226380702951226108116666172815817157023611889303668166839919156_
    3797683877845690114843122753427426880591799883780255338278664578660218_
    5045895962670442011443630321460259486764674312436994856054301765557425_
    1371150213401051058408679874766352952749178734973676859834707623881634_
    6251471489942512878190574323531299070406930309477389251738705417680653_
    1183648189451892725726445949589759600705334767585389769924857630972963_
    9976364832442643512622073858780110731539833099817555775136008111170797_
    6250597322951308884900670113339167641953793994512377610306198429310933_
    1214632141683542607746641232089854815064629129596536997380608256428801_
    9784909897301658268809203555030692846151917069465607257641149187197651_
    0905515966840312411845543650593021402849221691341852819791233589301994_
    1012291773441794027493574651881059432274494354092231954894280742068472_
    7146192942133436054611475404867886313250114399681532753236429290625909_
    3411000391368336312138915621701535954814084208794241665492294270773347_
    6055878415765927582014214726584822236443691314366097570085473354584000_
    9985915190584047337934331297339403392719579093995842312746836871169674_
    9786460913411872527166990047126222109345933847358924230951718379883743_
    2563465487604170316077418754242710065269818190591271690695446633836120_
    3745255515267088218383996330164203403732365333352120338272021319718003_
    5994220458994876460018350270385634117807768745161622933834063145505621_
    9106004731529642292049578901
     /
    342999030
                                                   Type: Fraction Integer

(52) -> b 60
           1215233140483755572040304994079820246041491
   (52)  - -------------------------------------------
                             56786730
                                                   Type: Fraction Integer

```
> 1 votes

# Answer
# APL(NARS), 83 chars, 166 bytes

```
r←B w;i
r←,1⋄i←0x⋄w+←1
→3×⍳w≤i+←1⋄r←r,1-+/{(1+i-⍵)÷⍨(⍵!i)×r[⍵+1]}¨0..i-1⋄→2
r←r[i]

```

Input as integer output as big rational

```
  B 0
1
  B 1
1r2
  B 2
1r6
  B 3
0
  B 4
¯1r30
  B 10
5r66
  B 100
¯94598037819122125295227433069493721872702841533066936133385696204311395415197247711r33330
  B 1000
¯1824310473866188725457264025685778887933833686704290605219715815764112625726249111586574725773210697096154899246
  27495522908087488299539455188791856758224155166849269724418491401224257983095561709862992465225174097919156
  37226361428342780548971002281045465308441161372350696920220116244179176068026260201962026025579005841653927
  13328528060009666284676390683434226380702951226108116666172815817157023611889303668166839919156379768387784
  56901148431227534274268805917998837802553382786645786602185045895962670442011443630321460259486764674312436
  99485605430176555742513711502134010510584086798747663529527491787349736768598347076238816346251471489942512
  87819057432353129907040693030947738925173870541768065311836481894518927257264459495897596007053347675853897
  69924857630972963997636483244264351262207385878011073153983309981755577513600811117079762505973229513088849
  00670113339167641953793994512377610306198429310933121463214168354260774664123208985481506462912959653699738
  06082564288019784909897301658268809203555030692846151917069465607257641149187197651090551596684031241184554
  36505930214028492216913418528197912335893019941012291773441794027493574651881059432274494354092231954894280
  74206847271461929421334360546114754048678863132501143996815327532364292906259093411000391368336312138915621
  70153595481408420879424166549229427077334760558784157659275820142147265848222364436913143660975700854733545
  84000998591519058404733793433129733940339271957909399584231274683687116967497864609134118725271669900471262
  22109345933847358924230951718379883743256346548760417031607741875424271006526981819059127169069544663383612
  03745255515267088218383996330164203403732365333352120338272021319718003599422045899487646001835027038563411
  78077687451616229338340631455056219106004731529642292049578901r342999030

```
> 1 votes

# Answer
# Haskell, 95 bytes

```
import Data.Ratio
p=product
b m=sum[p[k-v+1..k]*(v+1)^m%(p[-v..0-1]*(k+1))|k<-[0..m],v<-[0..k]]

```

This implements the explicit definition of Bernoulli numbers outlined on the Wikipedia page.
> 0 votes

# Answer
## Perl 6, 83 bytes

```
my &B={$^m??1-[+] (^$m).map: {combinations($m,$_)*B($_)/($m+1-$_)}!!1};say B slurp;

```

A faster, 114-byte solution:

```
my @b=1;for 1..+slurp() {@b.push: 1-[+] (^$^m).map: {([*] $m+1-$_..$m)*@b[$_]/($m+1-$_)/([*] 1..$_)}};say @b[*-1];

```
> 0 votes

# Answer
## Javascript, 168 bytes

```
function h(b,a){return a?h(a,b%a):b}for(var c=[],a=[],e=0,b,d,f,g;e<=k;)for(c[b=d=e]=1,a[e]=++e;d;)f=c[--d]*a[b]-(c[b]*=g=a[d]),r=h(f*=b,g=a[b]*=g),c[d]=f/r,a[--b]=g/r;

```

Set the 'k' variable to the Bernoulli number you want, and the result is c\[0\] over a\[0\]. (numerator & denominator)

## Sample Usage

```
k = 2;
console.log(c[0] + "/" + a[0]);

```

Not as small as the others, but the only one I've written that comes close. See https://marquisdegeek.com/code\_ada99 for my other (non-golf) attempts.
> 0 votes

# Answer
# Axiom, 57 bytes

```
g(n)==factorial(n)*coefficient(taylor(t*%e^t/(%e^t-1)),n)

```

code for test and results

```
(18) -> [[i, g(i)]  for i in 0..29]
   (18)
              1      1                1              1                1
   [[0,1], [1,-], [2,-], [3,0], [4,- --], [5,0], [6,--], [7,0], [8,- --],
              2      6               30             42               30
                5                  691               7                 3617
    [9,0], [10,--], [11,0], [12,- ----], [13,0], [14,-], [15,0], [16,- ----],
               66                 2730               6                  510
                43867                 174611               854513
    [17,0], [18,-----], [19,0], [20,- ------], [21,0], [22,------], [23,0],
                 798                    330                  138
          236364091               8553103                 23749461029
    [24,- ---------], [25,0], [26,-------], [27,0], [28,- -----------], [29,0]]
             2730                    6                        870
                                       Type: List List Expression Integer

(19) -> g 60
           1215233140483755572040304994079820246041491
   (19)  - -------------------------------------------
                             56786730
                                                 Type: Expression Integer

```

one has to note that the function is not the one someone wrote above but `t*%e^t/(%e^t-1))` with %e Euler costant
> 0 votes

# Answer
# Pyth, 22 bytes

```
L?b-1sm*.cbdcyd-btdUb1

```

Try it online!

Defines a function that is called as `y<number>`, e.g. `yQ`.

```
L                      # y=lambda b:
 ?b                  1 # ... if b else 1
   -1                  # 1 -
     s                 #     sum(
      m            Ub  #         map(lambda d: ... , range(b))
       *.cbd           #           combinations(b, d) *
            cyd        #             y(d) /      (float division)
               -btd    #                    b - (d - 1)

```
> 0 votes

---
Tags: code-golf, math, sequence, combinatorics
---


# Question
Title: Give me the Gray Code list of bit width n
The Gray Code is a sequence of binary numbers of bitwidth `n` where successive numbers differ only in one bit (see example output).

Reference

Example input:

```
3

```

Example output:

```
000
001
011
010
110
111
101
100

```

Notes:

* This question seems to have a dupe but it's not, for that question is not a code-golf, and it demands different output. It will help to check out it's answers, though.
* You may assume a variable `n` which contains the input.

# Answer
## JavaScript (77)

```
for(i=0;i<1<<n;)alert((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))

```

More browser-friendly version (console.log and prompt()):

```
n=prompt();for(i=0;i<1<<n;)console.log((Array(n*n).join(0)+(i>>1^i++).toString(2)).substr(-n))

```
> 2 votes

# Answer
# Python 2 (47)

```
for i in range(2**n):print bin(2**n+i/2^i)[3:]

```

The expression `i/2^i` for the `i`'th gray code number is from the this answer. To add leading zeroes that pad to length `n`, I add `2**n` before converting to a binary string, creating a string of length `n+1`. Then, I truncate the leading `1` and number type prefix `0b` with `[3:]`.
> 2 votes

# Answer
# APL (Dyalog Classic), 11 bytes

```
2≠/0,↑,⍳n⍴2

```

Try it online!

`n⍴2` is `2 2...2` \- a vector of `n` twos

is the indices of an `n`-dimensional array with shape `2 2...2` \- that is, a 2×2×...×2 array of nested vectors. As we use 0-indexing (`⎕IO←0`), those are all binary vectors of length `n`.

`,` flatten the 2×2×...×2 shape, so we get a *vector* of 2n nested binary vectors

"mix" - convert the vector of vectors to a solid 2n×n matrix. It looks like this:

```
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

```

`0,` prepends zeroes to the left of the matrix

`2≠/` computes the pairwise (`2`) xor () along the last dimension (`/` as opposed to ); in other words, every element gets xor-ed with its right neighbour, and the last column disappears

```
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

```
> 2 votes

# Answer
# K (ngn/k), 10 bytes

```
+~0=':!n#2

```

Try it online!
> 2 votes

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

```
2pU Ç^z)¤ùTU

```

Shaved off two bytes thanks to ETHproductions.

Try it online!
> 2 votes

# Answer
## F# ~~(86)~~ ~~(84)~~ (80)

```
for i in 0..(1<<<n)-1 do printfn"%s"(Convert.ToString(i^^^i/2,2).PadLeft(n,'0'))

```

This could probably be improved further.

Also note, if run in FSI, you'd need to `open System;;` first. If you'd like to avoid importing that, (and if you don't care about the order in which the values are printed) you can use this 82-character version:

```
for i in 0..(1<<<n)-1 do(for j in 0..n-1 do printf"%i"((i^^^i/2>>>j)%2));printfn""

```
> 1 votes

# Answer
## PowerShell(168)

Amateur PowerShell'r back with another attempt at golF! Hope you don't mind! At the very least these questions are fun, and a learning experience to boot. Assuming n has been inputted, we have:

```
$x=@('0','1');for($a=1;$a-lt$n;$a++){$x+=$x[($x.length-1)..0];$i=[Math]::Floor(($x.length-1)/2);0..$i|%{$x[$_]='0'+$x[$_]};($i+1)..($x.length-1)|%{$x[$_]='1'+$x[$_]}}$x

```

Because the PowerShell I'm working with is only 2.0, I can't use any bit shifting cmdlets which might make for shorter code. So I took advantage of a different method described in the question source, flipping the array and adding it to itself, appending a 0 to the front of the top half, and a 1 to the bottom half.
> 1 votes

# Answer
## Python - 54

Based off of an algorithm from the reference given in the challenge:

```
for i in range(2**n):print'{1:0{0}b}'.format(n,i>>1^i)

```

Ungolfed:

```
# For each of the possible 2**n numbers...
for num in range(2**n):
    gray = num>>1 ^ num

    # Print in binary and pad with n zeros.
    print '{1:0{0}b}'.format(grey)

```
> 1 votes

# Answer
### Ruby — ~~42~~ 39

Same algorithm, different language:

```
(2**n).times{|b|puts"%0#{n}b"%(b>>1^b)}

```

Switching from `#map` to `#times` as @voidpigeon suggests saves 3 characters.
> 1 votes

# Answer
# J, 24 bytes

```
[:#:@(22 b.<.@-:)[:i.2^]

```

Try it online!

Straightforward implementation of the "XOR with it's own floored half" algorithm. Note that `22 b.` is XOR.
> 1 votes

# Answer
# MATL, 10 bytes

```
W:qt2/kZ~B

```

Try it online!

The good old "XOR n with n\>\>2" method.

`W` \- compute 2^(input) (gets input implicitly)
`:q` \- create range of numbers from 0 to 2^n - 1
`t` \- duplicate that range
`2/k` \- MATL doesn't have bitshift, so divide (each number) by 2 and floor
`Z~` \- elementwise XOR that result with the original 0 to 2^n - 1 array
`B` \- convert each number in the result to binary
(Implicitly display output.)
> 1 votes

# Answer
# K (ngn/k), 25 bytes

```
{(x-1){,/0 1,''|:\x}/0 1}

```

Try it online!

---

* `|:\x`is "reverse scan x". applies reverse to x until the output equals the input, and shows each iteration. returns (0 1; 1 0) on first pass.
* `0 1,''` is "0 1 join each each". joins a 0 to each value of 1st elem, and 1 to each value of 2nd elem, giving ((0 0; 0 1);(1 1; 1 0)) on first pass
* `,/` is "join over", and flattens to list.
* `(x-1){...}/0 1`is "apply {func} over `0 1` x-1 times". takes the output of the last iteration as input
> 1 votes

# Answer
# APL (22)

```
{(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1

```

This outputs a n-by-2^n matrix containing the bits as its rows:

```
      n←3
      {(0,⍵)⍪1,⊖⍵}⍣(n-1)⍪0 1
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

```

Explanation:

* `{`...`}⍣(n-1)⍪0 1`: run the function `n-1` times with initial input the matrix `(0 1)T` (which is the 1-bit gray code)

+ `(0,⍵)`: each row of  with a `0` prefixed,
    + : on top of,
    + `1,⊖⍵`: each row of  with an `1` prefixed, in reversed order
> 0 votes

# Answer
# Jq 1.5, ~~105~~ 100 bytes

```
def g(n):if n<2then. else map([0]+.)+(reverse|map([1]+.))|g(n-1)end;[[0],[1]]|g(N)[]|map("\(.)")|add

```

Assumes N provides input. e.g.

```
def N: 3 ;

```

Expanded

```
def g(n):  # recursively compute gray code
  if n < 2
  then .
  else map([0]+.) + (reverse|map([1]+.)) | g(n-1)
  end;

  [[0],[1]]                 # initial state
| g(N)[]                    # for each element in array of gray codes
| map("\(.)")|add           # covert to a string

```

Try it online!
> 0 votes

# Answer
# Japt, 10 bytes

```
³Ç¤ÅÃf_Ê¥U

```

Try it online!
> 0 votes

# Answer
## T-SQL 134

This challenge is asking to return the Cartesian power of {(0),(1)}. This snippet builds the code which would execute the Cartesian product of {(0),(1)} n times.

```
DECLARE @ int=4,@s varchar(max)='SELECT*FROM's:set @s+='(VALUES(0),(1))t'+ltrim(@)+'(b)'if @>1set @s+=','set @-=1if @>0goto s exec(@s)

```
> -1 votes

---
Tags: code-golf, binary
---


title: Implement a Brute Force Sudoku Solver

text:
# Question
Title: Implement a Brute Force Sudoku Solver
Implement the shortest Sudoku solver using guessing. Since I have received a few request I have added this as an alternative question for those wishing to implement a brute force sudoku solver.

**Sudoku Puzzle:**

```
 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A|   3   |     1 |
B|     6 |       |   5
C| 5     |       | 9 8 3
-+-----------------------
D|   8   |     6 | 3   2
E|       |   5   |
F| 9   3 | 8     |   6
-+-----------------------
G| 7 1 4 |       |     9
H|   2   |       | 8
I|       | 4     |   3

```

**Answer:**

```
 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7

```

**Rules:**

1. Assume all mazes are solvable by logic only.
2. All input will be 81 characters long. Missing characters will be 0.
3. Output the solution as a single string.
4. The "grid" may be stored internally however you wish.
5. The solution must using a brute force guessing solution.
6. Solutions should solve within a reasonable time limit.

**Example I/O:**

```
>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137

```

# Answer
> 13 votes
# k (72 bytes)

Credit for this goes to Arthur Whitney, creator of the k language.

```
p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}

```

# Answer
> 10 votes
# Python, 188 bytes

This is a further shortened version of my winning submission for CodeSprint Sudoku, modified for command line input instead of stdin (as per the OP):

```
def f(s):
 x=s.find('0')
 if x<0:print s;exit()
 [c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
import sys
f(sys.argv[1])

```

If you're using Python 2, `'%d'%5**18` can be replaced with ``5**18`` to save 3 bytes.

To make it run faster, you can replace `'%d'%5**18` with any permutation of `'123456789'` at a cost of 1 byte.

If you want it to accept the input on stdin instead, you can replace `import sys;f(sys.argv[1])` with `f(raw_input())`, bringing it down to **177 bytes**.

```
def f(s):
 x=s.find('0')
 if x<0:print s;exit()
 [c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
f(raw_input())

```

**EDIT:** Here's a link to a more detailed walkthrough.

# Answer
> 9 votes
## Python, 197 characters

```
def S(s):
 i=s.find('0')
 if i<0:print s;return
 for v in'123456789':
  if sum(v==s[j]and(i/9==j/9or i%9==j%9or(i%9/3==j%9/3and i/27==j/27))for j in range(81))==0:S(s[:i]+v+s[i+1:])
S(raw_input())

```

# Answer
> 7 votes
# Perl, 120 bytes

Oh, I remember golfing that back in 2008... And it in fact stopped working in perl 5.12 since implicit setting of @\_ by split was removed then. So only try this on a sufficiently old perl.

Run with the input on STDIN:

```
sudoku.pl <<< "030001000006000050500000983080006302000050000903800060714000009020000800000400030"

```

`sudoku.pl`:

```
${/[@_[map{$i-($i="@-")%9+$_,9*$_+$i%9,9*$_%26+$i-$i%3+$i%9-$i%27}0..8%split""]]/o||do$0}for$_=$`.$_.$'.<>,/0/||print..9

```

# Answer
> 6 votes
# Answer in D:

```
import std.algorithm;
import std.conv;
import std.ascii;
import std.exception;
import std.stdio;

void main(string[] args)
{
    enforce(args.length == 2, new Exception("Missing argument."));
    enforce(args[1].length == 81, new Exception("Invalid argument."));
    enforce(!canFind!((a){return !isDigit(to!dchar(a));})
                     (args[1]),
                      new Exception("Entire argument must be digits."));

    auto sudoku = new Sudoku(args[1]);
    sudoku.fillIn();

    writeln(sudoku);
}

class Sudoku
{
public:

    this(string str) nothrow
    {
        normal = new int[][](9, 9);

        for(size_t i = 0, k =0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                normal[i][j] = to!int(str[k++]) - '0';
        }

        reversed = new int*[][](9, 9);

        for(size_t i = 0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                reversed[j][i] = &normal[i][j];
        }

        boxes = new int*[][](9, 9);
        indexedBoxes = new int*[][][](9, 9);

        for(size_t boxRow = 0, boxNum = 0; boxRow < 3; ++boxRow)
        {
            for(size_t boxCol = 0; boxCol < 3; ++boxCol, ++boxNum)
            {
                for(size_t i = 3 * boxRow, square = 0; i < 3 * (boxRow + 1); ++i)
                {
                    for(size_t j = 3 * boxCol; j < 3 * (boxCol + 1); ++j)
                    {
                        boxes[boxNum][square++] = &normal[i][j];
                        indexedBoxes[i][j] = boxes[boxNum];
                    }
                }
            }
        }
    }

    void fillIn()
    {
        fillIn(0, 0);
    }

    @property bool valid()
    {
        assert(full);

        for(size_t i = 0; i < 9; ++i)
        {
            for(int n = 1; n < 10; ++n)
            {
                if(!canFind(normal[i], n) ||
                   !canFind!"*a == b"(reversed[i], n) ||
                   !canFind!"*a == b"(boxes[i], n))
                {
                    return false;
                }
            }
        }

        return true;
    }

    override string toString() const
    {
        char[81] retval;

        for(size_t i = 0, k =0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                retval[k++] = to!char(normal[i][j] + '0');
        }

        return to!string(retval);
    }

private:

    @property bool full()
    {
        for(size_t i = 0; i < 9; ++i)
        {
            if(canFind(normal[i], 0))
                return false;
        }

        return true;
    }

    bool fillIn(size_t row, size_t col)
    {
        if(row == 9)
            return valid;

        size_t nextRow = row;
        size_t nextCol = col + 1;

        if(nextCol == 9)
        {
            nextRow = row + 1;
            nextCol = 0;
        }

        if(normal[row][col] == 0)
        {
            for(int n = 1; n < 10; ++n)
            {
                if(canFind(normal[row], n) ||
                   canFind!"*a == b"(reversed[col], n) ||
                   canFind!"*a == b"(indexedBoxes[row][col], n))
                {
                    continue;
                }

                normal[row][col] = n;

                if(fillIn(nextRow, nextCol))
                    return true;
            }

            normal[row][col] = 0;

            return false;
        }
        else
            return fillIn(nextRow, nextCol);
    }

    int[][] normal;
    int*[][] reversed;
    int*[][] boxes;
    int*[][][] indexedBoxes;
}

```

With the sample input, it takes **.033s** on my Phenom II X6 1090T when compiled with `dmd -w` (i.e. without optimizations), and it takes **.011s** when compiled with `dmd -w -O -inline -release` (i.e. with optimizations).

# Answer
> 4 votes
## Perl, 235 chars

```
$_=$s=<>;$r=join$/,map{$n=$_;'.*(?!'.(join'|',map+($_%9==$n%9||int($_/9)==int($n/9)||int($_/27)==int($n/27)&&int($_/3%3)==int($n/3%3)and$_<$n?'\\'.($_+1):$_>$n&&substr$s,$_,1)||X,@a).')(.).*'}@a=0..80;s!.!($&||123456789).$/!eg;say/^$r/

```

This is a golfed version of something I posted many years ago to the Fun With Perl mailing list: a sudoku-solving regexp.

Basically, it mangles the input into 81 lines, each containing all the numbers that could occur in the corresponding square. It then constructs a regexp to match one number from each line, using backreferences and negative lookahead assertions to reject solutions that violate the row, column or region constraints. Then it matches the string against the regexp, letting Perl's regexp engine do the hard work of trial and backtracking.

Astonishingly, it's possible to create a single regexp that works for any input, like my original program does. Unfortunately, it's quite slow, so I based the golfed code here on the hardcoded-givens version (found later in the FWP thread), which tweaks the regexp to reject early any solutions that it knows will later violate a constraint. This makes it reasonably fast for easy to moderate level sudokus, although particularly hard ones can still take a rather long time to solve.

Run the code with `perl -M5.010` to enable the Perl 5.10+ `say` feature. The input should be given on standard input, and the solution will be printed to standard output; example:

```
$ perl -M5.010 golf/sudoku.pl
030001000006000050500000983080006302000050000903800060714000009020000800000400030
832591674496387251571264983185746392267953418943812765714638529329175846658429137

```

# Answer
> 4 votes
# J, 103

```
'p n'=:(;#)I.0=a=:("."0)Y
((a p}~3 :'>:?n#9')^:([:(27~:[:+/[:(9=#@~.)"1[:,/(2 2$3),;.3],|:,])9 9$])^:_)a

```

*expected run time: O(gazillion billion years)*

# Answer
> 2 votes
1-liner coffee-script

`solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0`

Here is the bigger version with sample usage:

```
solve = (sudoku, cell = 0) ->
  if cell is 9*9 then return sudoku

  x = cell%9
  y = (cell - x)/9

  if sudoku[x][y] isnt 0 then return solve sudoku, cell+1

  row = (i) -> sudoku[x][i]
  col = (i) -> sudoku[i][y]
  box = (i) -> sudoku[x - x%3 + (i - i%3)/3][y - y%3 + i%3]

  good = (guess) -> [0...9].every (i) -> guess not in [row(i), col(i), box(i)]

  guesses = [1..9].filter good

  solves = (guess) -> sudoku[x][y] = guess; solve sudoku, cell+1

  (guesses.some solves) or sudoku[x][y] = 0

sudoku = [
  [1,0,0,0,0,7,0,9,0],
  [0,3,0,0,2,0,0,0,8],
  [0,0,9,6,0,0,5,0,0],
  [0,0,5,3,0,0,9,0,0],
  [0,1,0,0,8,0,0,0,2],
  [6,0,0,0,0,4,0,0,0],
  [3,0,0,0,0,0,0,1,0],
  [0,4,0,0,0,0,0,0,7],
  [0,0,7,0,0,0,3,0,0]
]
console.log if solve sudoku then sudoku else 'could not solve'

```

# Answer
> 1 votes
## D (322 chars)

For each unsolved square it builds an array of available options and then loops over it.

```
import std.algorithm,std.range,std.stdio;void main(char[][]args){T s(T)(T p){foreach(i,ref c;p)if(c<49){foreach(o;"123456789".setDifference(chain(p[i/9*9..i/9*9+9],p[i%9..$].stride(9),p[i/27*27+i%9/3*3..$][0..21].chunks(3).stride(3).joiner).array.sort)){c=o&63;if(s(p))return p;}c=48;return[];}return p;}s(args[1]).write;}

```

with whitespace:

```
import std.algorithm, std.range, std.stdio;

void main(char[][] args) {
    T s(T)(T p) {
        foreach (i, ref c; p) if (c < 49) {
            foreach (o; "123456789".setDifference(chain(
                    p[i/9*9..i/9*9+9],
                    p[i%9..$].stride(9),
                    p[i/27*27+i%9/3*3..$][0..21].chunks(3).stride(3).joiner
                ).array.sort))
            {
                c = o&63;
                if (s(p)) return p;
            }
            c=48;
            return [];
        }
        return p;
    }
    s(args[1]).write;
}

```

# Answer
> 1 votes
## Clojure - 480 bytes

The size exploded, but atleast it's a pretty number. I think it could be improved a lot by using just 1D-vector. Anyways, the test case takes a little under four seconds on my laptop. I thought it would be fitting to define a function, as it is a functional language after all.

```
(defn f[o &[x y]](if x(if(> y 8)(apply str(map #(apply str %)o))(first(for[q[(o y)]v(if(=(q x)0)(range 1 10)[(q x)])d[(assoc o y(assoc(o y)x v))]s[(and(every? true?(concat(for[i(range 9)](and(or(not=((d y)i)v)(= i x))(or(not=((d i)x)v)(= i y))))(for[m[#(+ %2(- %(mod % 3)))]r[(range 3)]a r b r c[(m y b)]e[(m x a)]](or(and(= e x)(= c y))(not=((d y)x)((d c)e))))))(f d(mod(+ x 1)9)(if(= x 8)(+ 1 y)y)))]:when s]s)))(f(vec(for[a(partition 9 o)](vec(map #(Integer.(str %))a))))0 0)))

```

Examples:

```
(f "030001000006000050500000983080006302000050000903800060714000009020000800000400030")
=> "832591674496387251571264983185746392267953418943812765714638529329175846658429137"
(f "004720900039008005001506004040010520028050170016030090400901300100300840007085600")
=> "654723981239148765871596234743819526928654173516237498482961357165372849397485612"

```

A slightly ungolfed (and prettier) version:

```
(defn check-place [o x y v]
  (and (every? true? (for [i (range 9)]
                       (and (or (not= ((o y) i) v) (= i x))
                            (or (not= ((o i) x) v) (= i y)))))
       (every? true?
         (for [r [(range 3)]
               a r
               b r
               c [(+ b (- y (mod y 3)))]
               d [(+ a (- x (mod x 3)))]]
           (or (and (= d x) (= c y)) (not= ((o y) x) ((o c) d)))))))

(defn solve-sudoku [board & [x y]]
  (if x
    (if (> y 8)
      (apply str (map #(apply str %) board))
      (first
        (for [v (if (= ((board y) x) 0) (range 1 10) [((board y) x)])
              :let [a (mod (+ x 1) 9)
                    b (if (= x 8) (+ 1 y) y)
                    d (assoc board y (assoc (board y) x v))
                    s (and (check-place d x y v) (solve-sudoku d a b))]
              :when s]
          s)))
    (solve-sudoku (vec (for [a (partition 9 board)]
                         (vec (map #(Integer. (str %)) a)))) 0 0)))

```

# Answer
> 1 votes
# PowerShell, ~~244~~ ~~242~~ ~~218~~ 215 bytes

```
$a=(24,24,6)*3|%{,(0..8|%{($r++)});,(0..8|%{$c%81;$c+=9});$c++;,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_}
$f={param($s)$l,$r=$s-split0,2;if($p=$a|?{$l.length-in$_}){1..9|?{"$_"-notin($p|%{$s[$_]})}|%{&$f "$l$_$r"}}else{$s}}

```

Try it online!

The script finds all solutions for a sudoku.

Unrolled:

```
$a=(24,24,6)*3|%{                       # array of indexes for a sudoku...
    ,(0..8|%{($r++)})                   # rows
    ,(0..8|%{$c%81;$c+=9});$c++         # columns
    ,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_   # and squares
}

$f = {
    param($s)

    # optional log. remove this statement in a release version.
    if($script:iter++ -lt 100 -or ($script:iter%100)-eq0){
        Write-Information ('{0}: {1,6}: {2}'-f (get-Date), $script:iter, ($s-replace0,' ')) -InformationAction Continue
    }

    $left,$right=$s-split0,2                # split by a first 0; $left.length is a position of this 0 if $s contains the 0
    if( $parts=$a|?{$left.length-in$_} ){   # get sudoku parts (rows, columns, squares) contain the position
        1..9|?{                             # try a digit
            "$_"-notin($parts|%{$s[$_]})    # all digits in these parts will be unique if parts do not contain the digit
        }|%{
            &$f "$left$_$right"             # recursive call with the digit
        } #|select -f 1                     # uncomment this to get a first result only
    }
    else{
        $s
    }

}

```

Test cases:

```
@(
    # 5 iterations, my notebook: 00:00:00, all
    # 5 iterations, my notebook: 00:00:00, first only
    , ( "832591674496387251571264983185746392267953418943812765714638529329175846658400030",
        "832591674496387251571264983185746392267953418943812765714638529329175846658429137" )

    # ~29600 iterations, my notebook: 00:01:27, all
    #  ~2100 iterations, my notebook: 00:00:10, first only
    # , ( "830001000006000050500000983080006302000050000903800060714000009020000800000400030",
    #     "832591674496387251571264983185746392267953418943812765714638529329175846658429137" )

    # ~49900 iterations, my notebook: 00:02:39, all
    # ~22400 iterations, my notebook: 00:01:20, first only
    # , ( "030001000006000050500000983080006302000050000903800060714000009020000800000400030",
    #     "832591674496387251571264983185746392267953418943812765714638529329175846658429137" )

) | % {
    $sudoku, $expected = $_
    $time = Measure-Command {
        $result = &$f $sudoku
    }
    "$($result-contains$expected): $time"
    $result
}

```

# Answer
> 1 votes
# J, 94 bytes

Works in exactly the same way as the K version, namely with a BFS (so it shall output all solutions). It prints spaces between output digits, but so does the K program. I’m not counting “s=:” as this is just naming the function (just like I wouldn’t count the filename in another language).

```
   s=: [:<@((]i.0:)}"0 _~(>:i.9)-.{&((+./ .=|:)3(],.[,@#.<.@%~)9 9#:i.81)@i.&0#])"1^:(0 e.,)@;^:_"."0

   s'030001000006000050500000983080006302000050000903800060714000009020000800000400030'
8 3 2 5 9 1 6 7 4 4 9 6 3 8 7 2 5 1 5 7 1 2 6 4 9 8 3 1 8 5 7 4 6 3 9 2 2 6 7 9 5 3 4 1 8 9 4 3 8 1 2 7 6 5 7 1 4 6 3 8 5 2 9 3 2 9 1 7 5 8 4 6 6 5 8 4 2 9 1 3 7

```

# Answer
> 0 votes
## Perl (195 chars)

```
use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9==$/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[$i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R

```

All credit goes to the creator here, and the explanation can be found there as well.

---
Tags: code-golf, game, puzzle-solver, sudoku
---


title: Is this n-speak?

text:
# Question
Title: Is this n-speak?
Inspired by Is it double speak?, I devised a harder challenge. Given a string, determine if the string is *n-speak*, for any \\$n\geq 2\\$.

N-speak is defined by repeating each letter \\$n\\$ times. With \\$n = 4\\$, the string `Hello` is transformed to `HHHHeeeelllllllloooo`. Your goal is to figure out if the input is a valid output for any n-speak transformation.

It should be noted that any sentence which is valid n-speak, for \\$n = 2k\\$, is also valid k-speak. Thus, the hard parts to solve will be odd values of \\$n\\$.

## Input

A string consisting of at least 2 characters. Input could also be a list of characters. Input is case sensitive.

## Output

`Truthy` if the string is n-speak, `falsey` otherwise.

## Examples

### True cases

```
HHeelllloo,,  wwoorrlldd!!
TTTrrriiipppllleee   ssspppeeeaaakkk
QQQQuuuuaaaaddddrrrruuuupppplllleeee    ssssppppeeeeaaaakkkk
7777777-------ssssssspppppppeeeeeeeaaaaaaakkkkkkk
999999999
aaaabb
aaaaaaaabbbbcc
aaaaabbbbb
@@@

```

If you want to generate additional truthy cases, you can use this MathGolf script. Place the string within the quotation marks, and the value of \\$n\\$ as the input.

### False cases

```
Hello, world!
TTTrrriiipppllleee   speak
aaaaaaaaaaaaaaaab
Ddoouubbllee  ssppeeaakk
aabbab
aaaabbb
a (does not need to be handled)
(empty string, does not need to be handled)

```

Of course, since this is code golf, get ready to trim some bytes!

# Answer
# APL (Dyalog Unicode), 12 bytes

Runs with `⎕io←0`

```
1≠∨/⍸2≠/∊0⍞0

```

Try it online!

Golfed together with Adám.

On the input (example: `"aaccccaaaaaabb"`, using `""` to denote a string (an array of chars) and `''` to denote a char)

`∊0⍞0` surround with 0s and flatten, `0 'a' 'a' 'c' 'c' 'c' 'c' 'a' 'a' 'a' 'a' 'a' 'a' 'b' 'b' 0`

`2≠/` perform pairwise not-equal, `1 0 1 0 0 0 1 0 0 0 0 0 1 0 1`

get the 0-indexed indices, `0 2 6 12 14`

`∨/` compute the GCD, `2`

`1≠` is this not equal to 1?
> 16 votes

# Answer
# Java 10, 85 bytes

```
s->{var r=0>1;for(int i=0;++i<s.length();)r|=s.matches("((.)\\2{"+i+"})*");return r;}

```

Regex ported from *@Arnauld*'s JavaScript answer.

Try it online.

**Explanation:**

```
s->{                          // Method with String parameter and boolean return-type
  var r=0>1;                  //  Result-boolean, starting at false
  for(int i=0;++i<s.length();)//  Loop `i` in the range [1, input-length):
    r|=                       //   Change the result to true if:
      s.matches("((.)\\2{"+i+"})*");
                              //    The input-String matches this regex
                              // NOTE: String#matches implicitly adds a leading ^ and
                              //       trailing $ to match the full String
  return r;}                  // After the loop, return the result-boolean

```

*Regex explanation:*

```
^((.)\2{i})*$                 // Full regex to match, where `i` is the loop-integer
^           $                 // If the full String matches:
  (.)                         //  A character
     \2{i}                    //  Appended with that same character `i` amount of times
 (        )*                  //  And that repeated zero or more times for the entire string

```
> 10 votes

# Answer
# Jelly, 5 bytes

```
Œɠg/’

```

Try it online!
> 8 votes

# Answer
# 05AB1E, 5 bytes

```
γ€g¿≠

```

Try it online!
> 8 votes

# Answer
# JavaScript (ES6), 53 bytes

Derived from the regular expression used by @wastl in *Is it double speak?*.

```
s=>[...s].some((_,n)=>s.match(`^((.)\\2{${++n}})*$`))

```

Try it online!

---

# Recursive version, 55 bytes

```
s=>(g=n=>s[++n]&&!!s.match(`^((.)\\2{${n}})*$`)|g(n))``

```

Try it online!

### Commented

```
s => (                    // s = input string
  g = n =>                // g is a recursive function taking a repetition length n
    s[++n] &&             // increment n; abort if s[n] is not defined
    !!s.match(            // otherwise, test whether s consists of groups of:
      `^((.)\\2{${n}})*$` //   some character, followed by n copies of the same character
    )                     //
    | g(n)                // or whether it works for some greater n
)``                       // initial call to g with n = [''] (zero-ish)

```
> 7 votes

# Answer
# Python 2, ~~73~~ ~~70~~ ~~69~~ 67 bytes

```
lambda s:s in[''.join(c*n for c in s[::n])for n in range(2,len(s))]

```

Try it online!

-4 bytes, thanks to Jitse
> 6 votes

# Answer
# QuadS, 16 bytesSBCS

```
1≠∨/⍵
(.)\1*
⊃⍵L

```

Try it online!

`1≠` is 1 different from

`∨/` the GCD

of the result of

`(.)\1*` PCRE Searching for any character followed by 0 or more repetitions thereof

`⊃⍵L` and returning the first of the match lengths (i.e. the length of the match)
> 5 votes

# Answer
# Stax, 5 bytes

```
╢b}▄;

```

Run and debug it

Procedure:

* Calculate run-lengths.
* GCD of array
* Is \> 1?
> 5 votes

# Answer
# T-SQL 2008 query, 193 bytes

```
DECLARE @ varchar(max)='bbbbbbccc';

WITH C as(SELECT number+2n,@ t
FROM spt_values
WHERE'P'=type
UNION ALL
SELECT n,stuff(t,1,n,'')FROM C
WHERE left(t,n)collate Thai_Bin=replicate(left(t,1),n))SELECT 1+1/~count(*)FROM C
WHERE''=t

```

**Try it online**
> 4 votes

# Answer
# Python 3, 69 bytes

```
lambda s:any(s=="".join(i*k for i in s[::k])for k in range(2,len(s)))

```

Try it online!
> 4 votes

# Answer
# PHP, ~~76~~ 75 bytes

```
while(($x=strspn($argn,$argn[$n+=$x],$n))>1&&($m=max($m,$x))%$x<1);echo!$x;

```

Try it online!

First attempt, a somewhat naïve iterative approach.

*Ungolfed:*

```
// get the length of the next span of the same char
while( $s = strspn( $argn, $argn[ $n ], $n ) ) {

    // if span is less than 2 chars long, input is not n-speak
    if ( $s < 2 ) {
        break;
    }

    // k is GCD
    $k = max( $k, $s );

    // if span length does not divide evenly into GCD, input is not n-speak
    if( ( $k % $s ) != 0 ) {
        break;
    }

    // increment current input string index
    $n += $s;

}

```

***-1 byte****, thx to @Night2!*
> 4 votes

# Answer
# Perl 6, ~~30~~ ~~27~~ 26 bytes

```
{1-[gcd] m:g/(.)$0*/>>.to}

```

Try it online!

Also uses the GCD trick, but uses the index of the end position of each run matched by the regex. Returns a negative number (truthy) if n-speak, zero (falsey) otherwise.
> 4 votes

# Answer
# Haskell, 48 bytes

```
import Data.List
f=(>1).foldr(gcd.length)0.group

```

Try it online!

Straightforward; uses the GCD trick.
> 4 votes

# Answer
# Red, 80 bytes

```
func[s][repeat n length? s[if parse/case s[any[copy t skip n t]][return on]]off]

```

Try it online!

## More idiomatic Red:

# Red, 81 bytes

```
func[s][any collect[repeat n length? s[keep parse/case s[any[copy t skip n t]]]]]

```

Try it online!
> 3 votes

# Answer
# Japt , 8 bytes

```
ò¦ mÊrÕÉ

```

Try it

```
ò¦ mÊrÕÉ     :Implicit input of string
ò            :Partition by
 ¦           :  Inequality
   m         :Map
    Ê        :  Length
     r       :Reduce by
      Õ      :  GCD
       É     :Subtract 1
             :Implicit output of boolean negation

```
> 3 votes

# Answer
# Brachylog, 5 bytes

```
ġz₂=Ṁ

```

Try it online!

Takes input through the input variable and outputs through success or failure.

At first I thought this would actually be *shorter* than my solution to Is it double speak?, but then I realized that `ġ` can and will try a group length of 1.

```
ġ        It is possible to split the input into chunks of similar length
 z₂      such that they have strictly equal length, and zipped together
    Ṁ    there are multiple results
   =     which are all equal.

```
> 3 votes

# Answer
# Kotlin, 78 bytes

```
{s->(2..s.length/2).any{i->s.chunked(i).all{z->z.length==i&&z.all{z[0]==it}}}}

```

Try it online!

## Explanation

```
{s->                      Take a string as input
  (2..s.length/2)         The each string needs two parts at least, prevents the case "aaa" is 3-speak
    .any{i->              If there is any n (in this case i) that is n-speak return true
      s.chunked(i)        Split into length i substrings
      .all{z->            All substrings z
        z.length==i       Should be completely full, ie. "aaa"->["aa","a"]
        &&                And
        z.all{            All chars (it)
          z[0]==it        Should be the same as the first char
        }
      }
    }
  }

```
> 3 votes

# Answer
# Scala, 80 bytes

```
s=>"(.)\\1*".r.findAllIn(s).map(_.size).reduce((x,y)=>(BigInt(x) gcd y).toInt)>1

```

Try it online!

PS. Original solution was based on `split` function but it's longer (83 bytes).

```
s=>(s+s).split("(.)(?!\\1)").map(_.size+1).reduce((x,y)=>(BigInt(x) gcd y).toInt)>1

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 34 bytes

```
GCD@@Length/@Split@Characters@#>1&

```

Try it online!
> 2 votes

# Answer
# Perl 5 `-p`, ~~83~~ ~~79~~ ~~76~~ 74 bytes

```
$_=s,(.)\1+,$t=length$&;$t/=2while$t%2-1;$r+=$t==($g||=$t);'',ge==$r&&/^$/

```

Try it online!
> 2 votes

# Answer
# Brain-Flak, 96 bytes

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

```

Try it online!

Uses the same GCD trick that many other submissions use. Output is 0 if the input is not n-speak, and a positive integer otherwise.

```
# For each character in the input
{

  # Add 1 to current run length
  <>({}())<>

  # If current and next characters differ:
  ({}[({})]){

    # Clean up unneeded difference
    {}<>

    # Move current run length to left stack, exposing current GCD on right stack
    ({}<>)

    # GCD routine: repeat until L=0
    {

      # Compute L mod R
      {(({})){({}[()])<>}{}}<>

      # Move R to left stack; finish computing L mod R and push to right stack
      ([{}()]({}<>)<>)

    }

    # Push 0 for new run length
    (<>)<>

  }{}

}

# Output GCD-1
<>{}({}[()])

```
> 2 votes

# Answer
# Oracle SQL, 182 bytes

```
select+1-sign(min(length(x)-(select sum(length(regexp_substr(x,'(.)\1{'||i||'}',1,level)))from t connect by level<length(x))))from(select x,level i from t connect by level<length(x))

```

It works with an assumption that input data is stored in a table t(x), e.g.

```
with t(x) as (select 'HHeelllloo,,  wwoorrlldd!!' from dual)

```
> 2 votes

# Answer
# K (ngn/k), ~~29~~ 23 bytes

```
{~|/(&/s@&1<s)!s:#'=:x}

```

Try it online!

edit: removed some unnecessary colons (i know when a monadic is required but it's not always clear to me if there's ambiguity so i default to including the colon) and changed the mod `x-y*x%y` to ngn/k's `y!x`, which meant i could remove a variable assignment
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~24~~ 22 bytesSBCS

Anonymous tacit prefix function.

```
⊂∊1↓⍳∘≢{⍵/⍨(≢⍵)⍴⍺↑⍺}¨⊂

```

Try it online!

enclose the string to treat map using the entire string
e.g. `"aaabbb"`

`⍳∘≢{` for each of the **ɩ**ndices 1 through the tally of characters in the string:
e.g. `3`

`⍺↑⍺` take the current number of elements from the current number, padding with 0s
e.g. `[3,0,0]`

`(≢⍵)⍴` cyclically **r**eshape into the shape of the tally of characters in the string
e.g. `[3,0,0,3,0,0]`

`⍵/⍨` use that to replicate the string's characters
`"aaabbb"`

`1↓` drop the first one (*n* = 1)

`⊂∊` is the the entire string a member of that list?
> 1 votes

# Answer
# Japt `-mR`, 12 bytes

```
ÊÆóXÃ¤d_äe e

```

Try it
> 1 votes

# Answer
# Retina 0.8.2, 28 bytes

```
M!`(.)\1*
.
.
^(..+)(\1|¶)*$

```

Try it online! Link includes test cases. Explanation:

```
M!`(.)\1*

```

Split the text into runs of identical characters.

```
.
.

```

Replace them all with the same character.

```
^(..+)(\1|¶)*$

```

Check whether the GCD of the lengths of the runs is greater than 1.
> 1 votes

# Answer
# MathGolf, 14 bytes

```
£─╞möl╠mÅ▀£╙╓┴

```

Try it online!

## Explanation

Checks all possible divisions of the input string into equal length chunks, and checks if there is a partition in which all chunks have just one unique character.

```
£                length of string with pop
 ─               get divisors
  ╞              discard from left of string/array (removes 1)
   mö            explicit map using 7 operators
     l           push input
      ╠          divide input into chunks of size k
       mÅ        explicit map using 2 operators
         ▀£      number of unique elements of list
           ╙     get maximum number of unique characters per chunk
                 loop ends here
            ╓    get the minimum of all maximums
             ┴   check if equal to 1

```
> 1 votes

# Answer
# Gaia, 10 bytes

```
ẋl¦d¦&⊢⌉1>

```

Try it online!

Same "GCD of run-lengths \> 1" as many other submissions use.

There is a bug in `ė` (run-length encoding) that drops the last unique element of the list, otherwise we could have the following 9 byte solution: `ė(¦d¦&⊢1>`.
> 1 votes

# Answer
# Pyth, 7 bytes

Outputs **0** for falsy inputs or a positive integer otherwise.

```
tiFhCr8

```

Try it online!
> 1 votes

# Answer
# Pyth, 8 bytes

```
<1iFhMr8

```

Try it online!

```
<1iFhMr8Q   Implicit: Q=eval(input())
            Trailing Q inferred
      r8Q   Run length encode Q into [count, character]
    hM      Take first element of each
  iF        Reduce by GCD
<1          Is 1 less than the above? Implicit print

```
> 1 votes

# Answer
# Perl 5 `-n`, 38 bytes

```
for$i(1..y///c){print/^((.)\2{$i})*$/}

```

Try it online!

The `print"\n"` in the footer is needed to separate the outputs.

Straightforward loop through all possible `n`s. Outputs nothing for "1-speak", anything else for n-speak where n \> 1.
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 76 bytes

```
s=>s.Where((_,n)=>s.Count%(n+=2)<1&!s.Where((c,i)=>c!=s[i/n*n]).Any()).Any()

```

Try it online!

Generate all `n` from 2, 3, 4, ... and do the following:

* Check if the length of input is divisible by n
* Compare each character of input to the corresponding character of an `n-speak` string

If both checks pass, the input string is `n-speak`.
> 1 votes

# Answer
# , 126 bytes

```
bool f(string s){import std.algorithm;auto a=s.group.minElement!(a=>a[1])[1];foreach(g;s.group)if(g[1]%a)return 0;return a>1;}

```

First code golf I've done in D.

Does not handle empty input strings (causes an assertion failure in the standard library).

Ungolfed version:

```
bool f(string s) {
    import std.algorithm; // for group and minElement

    // splits the string into a groups of the same character
    // eg. "HHHiii".group returns
    // [Tuple!(char, uint)('H', 3), Tuple!(char, uint)('i', 3)]
    auto groups = s.group;

    // gets the smallest group length
    auto min_length = groups.minElement!(a => a[1])[1];

    foreach(g; groups) // for each group
        if(g[1] % min_length) // if it's length is not divisible by smallest length
            return 0; // return false

    return min_length > 1; // return true if smallest length was above 1
}

```
> 1 votes

---
Tags: code-golf, string, decision-problem
---


title: I don't even... I only odd!

text:
# Question
Title: I don't even... I only odd!
Your task is simple: write a program that receives an integer as input and outputs it if it was odd, and does nothing otherwise (not halting is allowed). The challenge is, that you can only use odd bytes.

You can optionally append a trailing newline to the output.

This is code-golf, shortest answer in (odd) bytes wins.

Standard loopholes are forbidden. Furthermore, you cannot use versions of languages, which are newer than the posting of this challenge.

Example input \> output:

`13` \> `13`

`42` \>

# Answer
> 3 votes
# Japt `-f`, 1 byte

```
u

```

`u` has a char-code value of `117`.

Try it

# Answer
> 69 votes
# Lenguage, ~~645529908926937253684695788965635909332404360034079~~ ~~9394157991500940492270727190763049448735~~ ~~1174269748937617561533841898064735499551~~ 2293382937520069758100171520285996319 bytes

That's roughly equal to 2 duodecillion bytes.

The file translates to the following brainfuck program:

```
,[<<+>+>-]<[>>+<<-]+>>[-[->]<]<[<[<]>.<]

```

Takes input as an ASCII code, with a maximum value of 256. Uses wrapping.

# Answer
> 20 votes
# x86-64 Machine Code, 8 bytes

Inspired by Bruce Forte's solution, but slightly under par. :-)

```
8D 07          lea      eax, [rdi]    ; put copy of input parameter in EAX
D1 EF          shr      edi, 1        ; shift LSB into CF
             InfiniteLoop:
F3 73 FD       rep jnc  InfiniteLoop  ; test CF; infinite loop back here if input was even
C3             ret                    ; return with original input in EAX if it was odd

```

A single integer parameter is taken in the `EDI` register, following the System V AMD64 calling convention.

A copy of this value is initially made, and put into `EAX` so it can be returned if appropriate. (`LEA` is used instead of the normal `MOV` because we need an instruction with odd bytes.)

Then, the value in `EDI` is shifted right by 1, which places the shifted-off bit into the carry flag (CF). This bit will be 0 if the number was even, or 1 if it was odd.

We then test CF using the `JNC` instruction, which will branch only if CF is 0 (i.e., the number was even). This means that we will go into an infinite loop for even values. For odd values, we fall through and the original value (in `EAX`) is returned.

There is a bit of a trick with the `JNC` instruction, though—it has a `REP` prefix! Normally, `REP` prefixes are only used with string instructions, but because the Intel and AMD manuals both agree that irrelevant/superfluous/redundant `REP` prefixes are ignored, we throw one on the branch instruction here to make it 3 bytes long. That way, the relative offset that gets encoded in the jump instruction is also odd. (And, of course, `REP` is itself an odd-byte prefix.)

Thank goodness `RET` is encoded using an odd byte!

**Try it online!**

---

In case you don't think returning the value if it's odd or going into an infinite loop if it's even (so that you never return) satisfies the "output" requirements of the challenge, or you just want something more interesting, here's a function that outputs the value to a serial port (but only if it's odd, of course).

## x86-64 Machine Code (output to serial port), 17 bytes

```
8D 07         lea   eax, [rdi]   ; put copy of input parameter (EDI) in EAX

B1 F7         mov   cl, 0xf7     ; put 0xF7 into low-order bits of CX
B5 03         mov   ch, 0x03     ; put 0x03 into high-order bits of CX
FE C1         inc   cl           ; increment low-order bits of CX to 0xF8 (so all together it's now 0x3F8)
0F B7 D1      movzx edx, cx      ; move CX to DX ("MOV DX, CX" would have a 16-bit prefix of 0x66)

D1 EF         shr   edi, 1       ; shift LSB of input parameter into CF
73 01         jnc   IsEven       ; test CF: branch if 0 (even), fall through if 1 (odd)
EF            out   dx, eax      ; output EAX (original input) to I/O port 0x3F8 (in DX)
            IsEven:
C3            ret                ; return

```

What makes this a bit more interesting is that the code *does more*, which means it was more challenging to do it all using instructions that are encoded using only odd bytes. Of course, this also means that it fails at code golf, so it's kind of a tradeoff—do you want interesting and challenging, or do you want short?

Anyway, this uses the x86 `OUT` instruction to write to I/O port 0x3F8, which is the standard COM1 serial port on a PC. The fun part, of course, is that all standard I/O ports (serial and parallel) have even addresses, so they can't simply be encoded as immediates for the `OUT` instruction or moved directly into a register. You have to initialize with one less than the actual value, and then *increment* the value in the register. You're also limited to using certain registers for the manipulation because you need registers that are encoded using odd bytes in the instruction when used as operands.

Also, I had to initialize the `DX` register (via the `CX` register) at the top of the loop, even though this is only needed if the value is odd, to ensure that the `JNC` instruction would have an odd offset. However, since what we're skipping over is the `OUT` instruction, all this code does is waste cycles and clobber scratch registers; it doesn't actually *output* anything, so it doesn't break the rules.

Finally, this function will return (after having either done or not done the output to the serial port) with the input value left in `EAX`. But that doesn't actually break any rules; *all* functions in assembly language will return with a value in `EAX`—the question is just is it a *significant* value or a *garbage* value. That's determined by the function's documentation (essentially, does it return a value or does it return `void`), and in this case, I'm documenting it as not returning a value. :-)

No TIO link for this one, as it doesn't implement output to serial ports. You'll need real iron, or an imagination.

# Answer
> 19 votes
# Jelly, 2 bytes

```
ẋḂ

```

These characters correspond to bytes **0xF7** and **0xBF** in Jelly's code page.

Try it online!

# Answer
> 9 votes
# 05AB1E, 3 bytes

```
Éi=

```

The code corresponds to the byte values `C9,69,3D` or `201,105,61` which are all odd.

Try it online!

**Explanation**

```
É     # input % 2 == 1
 i    # if true
  =   # print without popping

```

# Answer
> 5 votes
# MATL, 3 bytes

```
o?G

```

MATL uses ASCII characters, so `o?G` corresponds to bytes (in decimal) `111`, `63`, `71`.

Try it online!

### Explanation

```
o     % Push (implicit) input modulo 2
?     % If nonzero
  G   %   Push input
      % End (implicit)
      % Display stack contents (implicit)

```

# Answer
> 5 votes
# Haskell, ~~36~~ 33 bytes

```
c[1]=1;c[m]=1+1+c[m-1-1];o	m=c[m]

```

Try it online!

Usage: `o 7` yields `7`, `o 8` enters an infinite loop.

The actual algorithm is

```
o 1 = 1
o m = 2 + o(m-2)

```

The first problem I faced was the lack of space and `(`, because a function `o` which takes an argument `m` is usually defined as `o m=...` or `o(m)=...`. However I found out that an inline comment `{- some comment -}` works as token delimiter too, so a definition `o{--}m=...` is possible under the given rules. *Edit: Ørjan Johansen pointed out that one can use a tab character instead of a space, saving three bytes:* `o m=...`

The second problem was the recursive call `o(m-2)`. `-2` is just `-1-1`, but here the comment trick does not work because the parentheses are required. I fixed this by letting the function work on a singleton list containing a number: `o[m-2]`, however, as this is not a standard way of providing input, I outsourced the computation to a helper function `c` which works on lists and call `c` from `o` which has the correct format.

# Answer
> 5 votes
# Python REPL, 38 bytes

Takes input as the value of the previous expression using `_`. Output will be a string (the string representation of the integer for odd, or the empty string for even).

```
'%s'%[['']+[_]][-1][[_%[1+1][-1]][-1]]

```

**Try it online**

To run it in an actual shell, you can try it here. Type the input, hit enter. Paste the code, hit enter.

### Explanation:

This took a while to figure out. There's no multiplication, no branching, no slicing, no commas, no periods, no imports, no parentheses, no `exec`, no `eval`, no `print`, and no functions. I got one solution working that output using stderr, but then I realized we had to output the actual integer, not just a truthy/falsey value.

I use brackets in place of parentheses with `[expression][-1]`. Simplifying that turns the above code into `'%s'%(['']+[_])[_%(1+1)]`.

Since there can be no commas, I used list addition to create `['',_]`. Using string formatting, the desired result is obtained.

# Answer
> 4 votes
# Cubix, ~~23~~ ~~19~~ 17 bytes

```
;;u!I1)%/;O=!;;/;

```

Try it!

`@`, which terminates a Cubix program, is ascii 64, so unfortunately this actually just enters an infinite loop after testing for oddness. No TIO link since it'll time out.

`=` (ascii 61) is a no-op in Cubix.

This is a slight modification of the prior algorithm (same # of bytes) that actually works for negative integers.

Cube version:

```
    ; ;
    u !
I 1 ) % / ; O =
! ; ; / ; . . .
    . .
    . .

```

Algorithm:

* `I` `(73)` : read in input as number
* `1` `(49)` : push 1
* `)` `(41)` : increment
* `%` `(37)` : take the mod
* `/` `(47)` : turn left
* `!` `(33)` : skip next instruction if odd
    + `1;;/;` `;` is `(59)` : prepares the stack for output
    + `O` `(79)` : Output as a number.
    + Then it re-enters the algorithm but `I` reads a `0` for end of input, so we are guaranteed to enter the even branch
* `u` `(117)` : right-hand u-turn
* `;;;!I` : loop, effectively doing nothing.

# Answer
> 4 votes
# CJam, 6 bytes

```
q_iY%%

```

`113` `95` `105` `89` `37` `37`

This program takes the mod 2 of the input (call it *r*) and prints every *r* th character in the input string. If the input number is odd, it prints the whole string, but if asked to print every 0th character the program throws an error.

Try it here

# Answer
> 3 votes
# Charcoal, 9 bytes

```
¿﹪Ｉθ÷χ⁵→θ

```

Try it online!

Basically it prints rightwards the input if it is not a multiple of 10/5 (the `²` char is even in the Charcoal code page). The characters used are:

* `¿`: code `BF`.
* : code `A5`.
* : code `C9`.
* `θ`: code `F1`.
* `÷`: code `AF`.
* `χ`: code `E3`.
* : code `B5`.
* : code `13`.

In fact the  near the end is redundant but then I saw that the answer had to have an odd length...

Explanation:

```
¿      if (
 ﹪      Modulo (
  Ｉθ      the input as number,
  ÷χ⁵      χ (predefined value: 10) divided by 5 = 2 ) [is 1])
 →θ      then print rightwards the input as string

```

# Answer
> 3 votes
# x86\_64 machine code (Linux), ~~12~~ 11 bytes

Unfortunately `0x80` is even, but it still worked out (assuming "does nothing" means not to return):

```
0000000000000000 <odd>:
   0:   8d 07                   lea  (%rdi), %eax
   2:   83 e7 01                and    $0x1, %edi
   5:   83 ff 01                cmp    $0x1, %edi
   8:   75 fb                   jne       5  <odd+0x5>
   a:   c3                      retq

```

-1 byte, thanks @CodyGray!

Try it online!

# Answer
> 3 votes
## Mathematica, 20 bytes

Appear to be the first solution in non-golfing language.

```
a=1+1;g[i_/;!a\[Divides]i]=i

```

In `MacintoshChineseTraditional` character encoding. `\[Divides]` is `{161, 253}` (2 bytes)

Alternative version (23 bytes)

```
\[CapitalAlpha]=1+1;\[CapitalGamma][\[CapitalChi]_/;\[CapitalAlpha]\[LeftFloor]\[CapitalChi]/\[CapitalAlpha]\[RightFloor]\[NotEqual]\[CapitalChi]]=\[CapitalChi]

```

or (shown in Unicode)

```
Α=1+1;Γ[Χ_/;Α⌊Χ/Α⌋≠Χ]=Χ

```

in `Symbol` character encoding. (use only 1-byte characters)

The solution defines a function `g` (or `Γ`) that, evaluate to input when the input is odd, and literally "do nothing" (does not evaluate) when the input is even.

# Answer
> 3 votes
## Perl, 54 bytes

**Requires `-E`.**

I really really enjoyed this challenge, I think I'd like to try and improve this answer, but I think that's might be the shortest I can make for now. I've been playing with these answers on and off for a few days now, but feel I'm happy with the 54 byte solution!

```
s//A_=Y[;A_=A_%O?A_W''/;y/#A-_/#-A/;s/[#-}]+/uc/ee;say

```

Try it online!

### Explanation

By default, most of Perl's string functions work on `$_`, which is empty to start.

First, `s//A_=Y[;A_=A_%O?A_W''/` replaces the empty string in `$_` with `A_=Y[;A_=A_%O?A_W''`, then `y/#A-_/#-A/` replaces characters based on the following list (char above becomes char below):

```
#ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
#$%&'()*+,-./0123456789:;<=>?@A

```

which updates `$_` to contain `$_=<>;$_=$_%2?$_:''`. Next `s/[#-}]+/uc/ee` replaces all chars `[#-}]+` with `uc`. Without the `/ee` this would just be the string `uc`, but `/ee` evaluates the contents of the string twice. The first evaluation returns the result of `uc`, which is an uppercase version of `$_` but since `$_` contains no alphabetic characters, this just returns the whole string, then the second `/e` evaluates the string again, which sets `$_` to either `$_` (the input number) or `''` depending on whether or not the number is odd or even.

Finally, since `$_` now contains what we want, we call `say` (which is what requires `-E` instead of `-e`) which prints `$_` followed by a newline.

---

### Alternative Perl, 93 bytes

**92 bytes code + 1 for `-p`, which I feel would make it non-competing.**

```
s//_/g;s//uc/e;y/\x09-\x0b/_/;s/____/}[/;s/___/%C]/;s/_/{''H/;y/'{}1CDGH/'-)1-3+--/;s/[#-}]+/uc/ee

```

Contains a tab and a vertical tab in the `y///`, indicated as `\x09` and `\x0b`.

Try it online!

# Answer
> 2 votes
# LOGO, ~~390~~ ~~46~~ ~~52~~ 50 bytes

```
[ask    1   se[make]iseq    1-3 cos ?/ask   1[1/sum 1   179]?]

```

That is a template-list that return the input if the input is odd, and cause an error if the input is even.

Usage:

```
show invoke [ask ... (paste code here) ... ] 5

```

output

```
5

```

since 5 is odd, and

```
invoke [ask ... (paste code here) ... ] 6

```

will cause an error because 6 is even.

---

# Answer
> 2 votes
## TI-BASIC, 14 bytes

```
Input Q
sinֿ¹(gcd(Q²,int(e
Q

```

This throws a domain error (printing nothing to the homescreen) on an even number.

```
Input Q             Q is a variable with an odd code. We cannot use "Ans" as it's even.

            int(e   floor(e) = 2; "2" is even.
         Q²         Q may be negative, so we square it which preserves parity.
     gcd(Q²,int(e   1 if Q is odd; 2 if Q is even.
sinֿ¹(gcd(Q²,int(e   Error iff Q is even.

Q                   If there was no error, print Q.

```

# Answer
> 1 votes
# Pyth, ~~14~~ ~~11~~ ~~10~~ 9 bytes

```
~~I+Q_+K/Q+3_1KQ~~
~~I!sIcQ+3_1Q~~
~~I!u+1_GQ1Q~~
?u+1_GQ1k

```

Test suite.

# Answer
> 1 votes
# Japt, 4 bytes

```
u)çU

```

Japt uses ISO/IEC 8859-1, so this corresponds to (in decimal) `117 41 231 85`.

Test it online!

### Explanation

```
Uu)çU   Implicit: U = input integer
Uu)     Return Python-style U % (missing argument = 2). This gives 1 if U is odd, 0 if even.
   çU   Implicitly convert U to a string and repeat it that many times.
        Implicit: output result of last expression

```

I first tried solutions using `p`, which is basically `ç` with reversed arguments. However, `p` performs exponentiation if its left argument is a number, so we'd need to explicitly convert it to a string. This solution turns out to actually be a byte shorter, in addition to not containing any odd bytes.

# Answer
> 1 votes
# dc, 21 bytes

```
[c]sa?kKKCI-1;1k%1!=a

```

Decimal: `91 99 93 115 97 63 107 75 75 67 73 45 49 59 49 107 37 49 33 61 97`

As per this IO default, this program leaves the input on the main stack if it is odd and empties the stack otherwise. This can be confirmed by adding the `f` debug command to the end of the program as is the case on the TIO page.

Try it online!

## Explanation

```
[    # Begin macro definition.
 c   # Clear the main stack.
]sa  # End macro definition and push the macro into register "a".
?k   # Prompt for input and store it into precision parameter "k".
KK   # Push two copies of the input to the main stack.
CI-  # Push C-I = 12-10 = 2 to the main stack
1;1  # Push the value stored in the first index of array "1" (0 by default)
     # to the main stack.
k    # Push 0 into parameter "k" to reset the precision (otherwise the modulus
     # function will not work correctly).
%    # Push the input (mod 2) to the main stack.
1!=a # If the input (mod 2) does not equal 1, execute the macro in register "a".
f    # OPTIONAL: Output the contents of the main stack.

```

# Answer
> 1 votes
## TI-Basic, 18 bytes

Saved 2 bytes thanks to lirtosiast

```
:Prompt Q
:While 5Q/ᴇ1-int(5Q/ᴇ1
:Q

```

in bytes (+2 newlines = 3F)

```
:Prompt Q
 DD     51
:While 5Q/ᴇ1-int(5Q/ᴇ1
 D1    35 3B B1  35 3B
        51 31     51 31
         83 71     83
:Q
 51

```

See http://tibasicdev.wikidot.com/one-byte-tokens

# Answer
> 1 votes
# MathGolf, 3 bytes

```
¥{k

```

Try it online!

The used bytes are `157, 123, 107`.

### Explanation

```
¥     Input modulo 2
 {    Loop that many times
  k   Push input

```

# Answer
> 0 votes
# Bash, 31 bytes

```
read a
[ $[a%2] = 0 ] ||echo $a

```

Try it online!

# Explanation:

```
read a                   reading the input and define it on the variable a
[ $[a%2] = 0 ]      outputs exit status 0 when a/2 is 0 and exit status 1 if not.
||                           evaluates only when the exit status left of it is 1
echo $a                displays the variable a

```

---
Tags: code-golf, restricted-source
---