# Question
Title: How much present did you get for Christmas?
Yes, how *much*, not how many...

As we all know, a large present is far better than a small one. Therefore, the value of the presents should always be measured in total volume, not number of presents, weight, or even combined price.

As it's frowned upon to compare the amount of presents one gets, you don't want a long script that's easily seen and read by others at the Christmas party. Therefore you need to keep the number of bytes in your script at a minimum.

Your task is simple: **Create a program that takes a list of dimensions as input, on any suitable format, and outputs the combined volume of your presents.** The dimension of each present will either be a set of three numbers, or a single number. If the input is three numbers (`L, W, H`), the present is a cuboid of dimensions `L x W x H`. If it's a single number (`R`), the present is a sphere of radius `R`.

Rules:

* It can be either a full program or a function
* The input can be in any convenient format
    + If desirable, a sphere may be represented by a number followed by two zeros
    + A cuboid will always have all non-zero dimensions.
* The output should be a single decimal number
    + Additional output is accepted as long as it's obvious what the answer is
    + Output must have at least two digits after the decimal point
    + The output can be in standard form / scientific notation if the number is larger than 1000.
    + In case your language doesn't have a Pi-constant, the answer should be accurate up to 9999.99.

Examples:

```
((1,4,3),(2,2,2),(3),(4,4,4))
197.0973    // (1*4*3 + 2*2*2 + 4/3*pi*3^3 + 4*4*4)

(5)
523.5988

(5,0,0)
523.5988

```

---

## 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=67027,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
# Jelly, ~~19~~ 18 bytes

```
Zµ*3×1420÷339Ḣo@PS

```

Try it online!

Unfortunately, Jelly does not have a **π** constant yet, and the vectorizer doesn't handle floats properly.

To overcome these issues, instead of multiplying by **4π/3**, we multiply by **1420** and divide by **339**. Since **1420 ÷ 339 = 4.18879056…** and **4π/3 = 4.18879020…**, this is sufficiently precise to comply with the rules.

The newest version of Jelly could accomplish this task in **14 bytes**, with better precision.

```
Zµ*3×240°Ḣo@PS

```

Try it online!

### How it works

```
Zµ*3×1420÷339Ḣo@PS  Left argument: A, e.g., [[1, 2, 3], [4, 0, 0]]

Z                   Zip A; turn A into [[1, 4], [2, 0], [3, 0]].
 µ                  Begin a new, monadic chain with zip(A) as left argument.
  *3                Cube all involved numbers.
    ×1420           Multiply all involved numbers by 1420.
         ÷339       Divide all involved numbers by 339.
                    This calculates [[4.19, 268.08], [33.51, 0], [113.10, 0]]
             Ḣ      Head; retrieve the first array.
                    This yields [4.19, 268.08].
                P   Take the product across the columns of zip(A).
                    This yields [6, 0].
              o@    Apply logical OR with swapped argument order to the results.
                    This replaces zeroes in the product with the corresponding
                    results from the left, yielding [6, 268.08].
                 S  Compute the sum of the resulting numbers.

```

The non-competing version uses `×240°` instead of `×1420÷339`, which multiplies by **240** and converts the products to radians.
> 10 votes

# Answer
# Pyth, ~~19~~ 18 bytes

```
sm|*Fd*.tC\ð7^hd3Q

```

*1 byte thanks to Dennis*

Demonstration

Input format is list of lists:

```
[[1,4,3],[2,2,2],[3,0,0],[4,4,4]]

```

It simply multiplies the dimensions together to calculate the cube volume. If that comes out to zero, it calculates the sphere volume.

The sphere constant, `4/3*pi` is calculated as 240 degrees in radians. `.t ... 7` converts an input in degrees to radians, and `C\ð` calculates the code point of `ð`, which is 240.
> 9 votes

# Answer
## Haskell, 40 bytes

```
q[x]=4/3*pi*x^^3
q x=product x
sum.map q

```

Usage example: `sum.map q $ [[1,4,3],[2,2,2],[3],[4,4,4]]` -\> `197.09733552923254`.

How it works: For each element of the input list: if it has a single element `x` calculate the volume of the sphere, else take the `product`. Sum it up.
> 9 votes

# Answer
# Python 2, ~~86~~ 70 bytes

```
lambda i:sum(x[0]*x[1]*x[2]if len(x)>1 else x[0]**3*4.18879for x in i)

```
> 7 votes

# Answer
## Mathematica, 34 bytes

```
Tr[1.##&@@@(#/.{r_}:>{4r^3/3Pi})]&

```

An unnamed function which takes a nested list of lengths and returns the volume as a real number.

We first replace single values with the volume of the corresponding sphere with `/.{r_}:>{4r^3/3Pi}`. Then we multiply up the contents of each list with `1.##&@@@`. Finally we compute the sum as the trace of the vector with `Tr[...]`.
> 5 votes

# Answer
# JavaScript (ES6), 56

```
l=>l.map(([x,y,z])=>t+=y?x*y*z:x*x*x*4/3*Math.PI,t=0)&&t

```

The more *sensible* `.reduce` version is 1 byte longer

```
l=>l.reduce((t,[x,y,z])=>t+(y?x*y*z:x*x*x*4/3*Math.PI),0)

```
> 5 votes

# Answer
## Python, 49 bytes

```
lambda l:sum(a*b*c or a**3*4.18879for a,b,c in l)

```

Uses the representation of spheres as `(a,0,0)`. Treated as a cuboid, this has volume 0, in which case the sphere volume is used instead. I'm not clear on how accurate the constant needs to be, so I hope this is enough.
> 5 votes

# Answer
# MATL, 20 bytes

```
it!ptbw~)3^4*3/XT*hs

```

Input format is a matrix in which each row describes a cube or a sphere. A sphere is defined by only the first number in that row; the other two numbers are zero. So the first example from the challenge would be:

```
[1 4 3; 2 2 2; 3 0 0; 4 4 4]

```

This uses the current release of the language, 2.0.2, which is earlier than this challenge.

### Examples:

```
>> matl it!ptbw~)3^4*3/XT*hs
> [1 4 3; 2 2 2; 3 0 0; 4 4 4]
197.0973355292326

>> matl it!ptbw~)3^4*3/XT*hs
> [5 0 0]
523.5987755982989

```

### Explanation:

```
i             % input matrix
t!            % duplicate and transpose: each object is now a column
p             % product of elements in each column
t             % duplicate
b             % bubble up top-third element in stack
w             % swap top two elements in stack
~             % logical 'not'. This gives logical index of speheres
)             % reference () indexing. This is a logical-linear index to get sphere radii
3^4*3/XT*     % formula for volume of spehere; element-wise operations
h             % horizontal concatenation
s             % sum

```
> 4 votes

# Answer
# Prolog, ~~115~~ 100 bytes

**Code:**

```
[]*0.
[[L,W,H]|T]*V:-W=0,X is 4*pi*L^3/3,T*Y,V is X+Y;X is L*W*H,T*Y,V is X+Y.
p(L):-L*V,write(V).

```

**Explained:**

```
[]*0.
[[L,W,H]|T]*V:-W=0,                           % When 2nd dimension is 0
                  X is 4*pi*L^3/3,            % Calc volume of sphere
                  T*Y,                        % Recurse over list
                  V is X+Y                    % Sum volumes
                  ;                           % When we have a cube
                  X is L*W*H,                 % Calc cube volume
                  T*Y                         % Recurse over list
                  V is X+Y.                   % Sum volumes
p(L):-L*V,                                    % Get combined volume of list of lists
      write(V).                               % Print volume

```

**Examples:**

```
p([[1,4,3],[2,2,2],[3,0,0],[4,4,4]]).
197.09733552923257

p([[5,0,0]]).
523.5987755982989

```

Try it online here

Edit: saved 15 bytes by defining a dyadic predicate.
> 3 votes

# Answer
## Perl, ~~52~~ 47 bytes

```
s/,/*/g||s@$@**3*4.18879@,$\+=eval for/\S+/g}{

```

*46 + 1 for `-p` (that's been common; let me know if it's different here and I'll update)*

Usage: put in a file and `echo 1,4,3 2,2,2 3 4,4,4 | perl -p x.pl`

With comments:

```
s/,/*/g                # x,y,z becomes x*y*z
||                     # if that fails,
s@$@**3*1420/339@      # x becomes x**3 * 1420/339
,                      #
$\+=eval               # evaluate the expression and accumulate
for/\S+/g              # iterate groups of non-whitespace
}{                     # -p adds while(<>){...}continue{print}; resets $_

```

**update 47** Thanks to @Dennis for saving some bytes using this trick.
> 3 votes

# Answer
## CJam, ~~24~~ 21 bytes

```
q~{3*)4P*3/*+3<:*}%:+

```

Test it here.

### Explanation

```
q~       e# Read and evaluate input.
{        e# Map this block over the list of presents...
  3*     e#   Repeat the list of lengths 3 times. This will expand cuboids to 9 elements
         e#   and spheres to three copies of the radius.
  )      e#   Pull off the last element.
  4P*3/* e#   Multiply by 4 pi / 3.
  +      e#   Add it back to the list of lengths.
  3<     e#   Truncate to 3 elements. This is a no-op for spheres, which now have three
         e#   elements [r r 4*pi/3*r] but discards everything we've done to cuboids, such
         e#   that they're reduced to their three side lengths again.
  :*     e#   Multiply the three numbers in the list.
}%
:+       e# Sum all the individual volumes.

```
> 2 votes

# Answer
## PowerShell, 67 Bytes

```
($args|%{($_,((,$_*3)+4.18879))[$_.count-eq1]-join'*'})-join'+'|iex

```

Some black magic happening here. I'll try to walk through it smoothly.

We first take our input, expected as individual comma-delimited arrays e.g. `(1,4,3) (2,2,2) (3) (4,4,4)`, and pipe that into a loop `|%{}`.

Inside the loop, we first check whether `$_`, the particular array we're considering, has only one item and use that to index into an array (essentially a shorter if/else construction). If it's more than one item, suppose `(1,4,3)` as input, we execute the first half, which is simply to spit out the array via `$_`, such as `(1,4,3)`. Otherwise, we create a new dynamic array consisting of the element three times with `(,$_*3)` and tack on an approximation of 4/3rd\*Pi. For input `(3)`, this will result in `(3,3,3,4.18879)` output.

Yes, PowerShell has a Pi constant, accessed via .NET call `[math]::PI`, but that's longer and I don't want to use it. :p

Regardless, we concatenate that output array with asterisks via `-join'*'`, so `"1*4*3"`. Once we're completely through the loop, we now have a collection of strings. We `-join'+'` all those together for our addition, and `iex` the expression to calculate the result.

Phew.
> 2 votes

# Answer
# Ruby, 58 characters

```
->b{b.reduce(0){|t,s|a,b,c=*s;t+(c ?a*b*c :a**3*4.18879)}}

```

Sample run:

```
2.1.5 :001 ->b{b.reduce(0){|t,s|a,b,c=*s;t+(c ?a*b*c :a**3*4.18879)}}[[[1,4,3],[2,2,2],[3],[4,4,4]]]
 => 197.09733

```

## Ruby, 50 characters

Improvement idea shamelessly stolen from edc65's JavaScript answer.

```
->b{t=0;b.map{|a,b,c|t+=c ?a*b*c :a**3*4.18879};t}

```

Sample run:

```
2.1.5 :001 > ->b{t=0;b.map{|a,b,c|t+=c ?a*b*c :a**3*4.18879};t}[[[1,4,3],[2,2,2],[3],[4,4,4]]]
 => 197.09733

```
> 1 votes

# Answer
# Japt, ~~27~~ 22 bytes

```
N®r*1 ª4/3*M.P*Zg ³} x

```

Takes input as space-separated arrays. Try it online!

### How it works

```
N®   r*1 ª 4/3*M.P*Zg ³  } x
NmZ{Zr*1 ||4/3*M.P*Zg p3 } x

          // Implicit: N = array of input arrays
NmZ{   }  // Map each item Z in N to:
Zr*1      //  Reduce Z with multiplication.
||4/3*M.P //  If this is falsy, calculate 4/3 times Pi
*Zg p3    //  times the first item in Z to the 3rd power.
x         // Sum the result.
          // Implicit: output last expression

```
> 1 votes

# Answer
# , 70 bytes

```
function(l)sum(mapply(function(x)prod(x*!!1:3)*4.18879^is.na(x[2]),l))

```

Try it online!
> 1 votes

# Answer
# Pip, 23 bytes

```
{$*a|4/3*PI*@a**3}MSg^s

```

There's a couple ways to give input to this program. It can take each present as a command-line argument of three space-separated numbers (which will need to be wrapped in quotes: `pip.py present.pip "1 4 3" "3 0 0"`). Alternately, specify the `-r` flag and give each present as a line of stdin consisting of three space-separated numbers. Try it online!

### How?

```
                         g is list of cmdline args (or lines of stdin, if using -r flag)
                         s is space, PI is what it says on the tin (implicit)
                    g^s  Split each argument on spaces, so we have a list of lists
{                }MS     Map this function to each sublist and sum the results:
 $*a                      Fold the list on * (i.e. take the product)
    |                     Logical OR: if the above value is zero, use this value instead:
     4/3*PI*              4/3 pi, times
            @a            First element of the list
              **3         Cubed
                         Autoprint the result

```
> 1 votes

# Answer
# Perl 5, 142 bytes

Run with `-p` in the command line, and type numbers delimited with a comma, like so:

`5,0,0` or `(5,0,0)`

would produce

`523.598820058997`

There is no `pi` keyword in Perl. This is, in most cases, accurate to the significant figures specified, however even if I typed in all the figures of pi I know, it wouldn't be very accurate for some calculations. So I left it with `3.1415`. I'm unsure if this is acceptable or not.

Code:

```
@a=$_=~/(\d+,*)/g;$_=0;@n = map(split(/\D/),@a);for($i=0;$i<$#n;$i+=3){$x=$n[$i];$n[$i+1]==0?$_+=1420/339*$x**3:$_+=($x*$n[$i+1]*$n[$i+2]);}

```

Edited for greater precision on the advice of Dennis, who is better at basic mathematics than I, and from a suggestion by MichaelT to save bytes whilst remaining precise.
> 0 votes

# Answer
# Lua, ~~115~~ 104 bytes

```
function f(a)b=0 for i=1,#a do c=a[i]b=b+(1<#c and c[1]*c[2]*c[3]or(4/3)*math.pi*c[1]^3)end return b end

```

Straightforward solution, I have to wrap the pseudo-ternary operation `<condition> and <non-false> or <value if false>` in parenthesis else b would sum with both areas.

Input must be in the form `array={{1,4,3},{2,2,2},{3},{4,4,4}}` and the result can be seen by executing `print(f(array))`.
> 0 votes

# Answer
## R, ~~38~~ 36 bytes

```
function(x,y=4*pi/3*x,z=x)sum(x*y*z)

```

Uses default arguments to switch between the cases: with three arguments computes the product, and with one argument computes the sphere formula.
> 0 votes

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

```
εDgi3m4žq*3/*]PO

```

Try it online.

**Explanation:**

```
ε                # Map each inner list of the (implicit) input to:
 D               #  Duplicate the current inner list
  gi             #  Is the length 1 (is it an `R`):
    3m           #   Take the duplicated current item and take its cube
                 #    i.e. [3] → [27]
      žq         #   PI
        4*       #   Multiplied by 4
          3/     #   Divided by 3
                 #    → 4.1887902047863905
            *    #   And multiply it with the current cubed `R`
                 #    [27] and 4.1887902047863905 → [113.09733552923254]
]                # Close both the if and map
 P               # Take the product of each inner list
                 #  i.e. [[1,4,3],[2,2,2],[113.09733552923254],[4,4,4]]
                 #   → [12,8,113.09733552923254,64]
  O              # Take the total sum (and output implicitly)
                 #  i.e. [12,8,113.09733552923254,64] → 197.09733552923254

```
> 0 votes

# Answer
# Japt `-mx`, 16 bytes

```
ÊÉ?U×:Um³*4/3*MP

```

Try it
> 0 votes

---
Tags: code-golf, math, arithmetic, geometry
---


# Question
Title: Find pairs of numbers with a particular LCM and GCD
I was working on a math question with a friend of mine, and we decided to write a script that finds the answer. The original question is as follows:

> The difference of two natural numbers is 2010 and their greatest common denominator is 2014 times smaller than their lowest common multiply. Find all the possible solutions.

We started writing the program independently of each other, and when it worked we decided to golf it up to get the least amount of bytes we could manage. We ended up with this beautiful line of code at a marvelous 89 bytes.

```
from fractions import*;print[i for i in range(10**6)if i*(i+2010)/gcd(i,i+2010)**2==2014]

```

We wanted to see if anyone manages to write a shorter piece of code, that enumerates the first 1 million i's. If you are brave enough to compete, you may use any language you like, but we would prefer Python 2 to be able to compare your code with ours.

Usual rules apply, shortest bytes win. The standard code golf loopholes apply. Standard "loopholes" which are no longer funny

Have fun!

# Answer
# Mathematica, 8 bytes

```
{4,5092}

```

Proof that 4 and 5092 are the only solutions: The original problem can be rewritten as

> x (x + 2010) = 2014 GCD(x, x+2010)2

Let's write *x* as 2a2 3a3 5a5… and *x* \+ 2010 as 2b2 3b3 5b5… Then the equation becomes

> 2a2+b2 3a3+b3 5a5+b5… = 2014 22min(a2,b2) 32min(a3,b3) 52min(a5,b5)

Since 2014 = 2 × 19 × 53, we have

> ap \+ bp = 2min(ap, bp) + { 1 if p ∈ {2, 19, 53}, 0 else }

Thus

> ap = bp if p ≠ 2, 19, 53
> ap = bp±1 else

Thus

> x + 2010 = 2±1 19±1 53±1 x

There are only 8 possible choices, and we could easily check that 4 and 5092 are the only positive integer solutions.

Wait, I hear people screaming standard loophole…

# Mathematica, 45 bytes

```
Select[Range[9^7],2014GCD[#,s=#+2010]^2==s#&]

```
> 22 votes

# Answer
## Pyth ~~27~~ 25

```
J2010fq+J4/*T+TJ^iTJ2U^T6

```

Try it online.

This uses your algorithm fairly naively... I might be able to come up with something better...

Basically filters out values that don't meet the criterion from `range(10**6)`

Thanks to @xnor for pointing out in chat that `gcd(x,x+2010)==gcd(x,2010)`
> 4 votes

# Answer
# Python 3, 84 bytes

FryAmTheEggman's already suggested how to make your solution 88 bytes so I won't post that. But I thought I'd show how you can get even fewer bytes in Python 3:

```
from fractions import*
x=10**6
while x:y=x+2010;x*y-gcd(x,y)**2*2014or print(x);x-=1

```

*(Thanks for FryAmTheEggman for tips)*

This doesn't work in Python 2 because `print`'s not a function.

I'm not sure if we're allowed, but if we could use `9**9` instead of `10**6` that'd be another byte.
> 3 votes

# Answer
## GolfScript (41 bytes)

> The difference of two natural numbers is 2010 and their greatest common denominator is 2014 times smaller than their lowest common multiple. Find all the possible solutions.

Call the numbers `am` and `bm` where `gcd(a, b) = 1` and wlog `b > a`. Then the difference is `m(b-a) = 2010`, and `lcm(am, bm) = abm = 2014m` so `ab=2014`.

Factors of 2014 are

```
1 * 2014
2 * 1007
19 * 106
38 * 53

```

and those which have differences that divide into 2010 are

```
1007 - 2 => m = 2, solution is 4, 2014
53 - 38 => m = 134, solution is 5092, 7102

```

Since I'm operating in a language which doesn't have built-in GCD or LCM, I think this analysis probably shortens the program:

```
44,{).2014{.2$/\@%!}:,~\2$- 2010,***}%0-`

```

where `44` is `floor(sqrt(2014))`.

It is possible to get quite close using a naïve loop:

```
10 6?,1>{.2010+.2${.@\%.}do;.*2014*@@*=},`

```
> 2 votes

# Answer
# R, 75 chars

```
for(a in 1:1e6){q=1:a;b=a+2010;if(a*b/max(q[!a%%q&!b%%q])^2==2014)print(a)}

```

With line breaks:

```
for(a in 1:1e6){
    q=1:a
    b=a+2010
    if(a*b/max(q[!a%%q&!b%%q])^2==2014)print(a)
    }

```
> 2 votes

# Answer
# Perl6 ~~61~~ ~~58~~ ~~56~~ ~~54~~ 52

A fairly direct translation of your source gives

```
for ^10**6 ->\i{i.say if i*(i+2010)/(i gcd(i+2010))**2==2014}

```

`gcd` is an infix op in Perl6.

`^10**6` is short for `0 ..^ 10**6`, where the `^` means exclude this number from the range.

---

Of course `i gcd (i+2010)` is the same as `i gcd 2010` so I can save 3 characters

```
for ^10**6 ->\i{i.say if i*(i+2010)/(i gcd 2010)**2==2014}

```

If I use `$_` instead of `i` I can save another couple of characters. ( `.say` is short for `$_.say` )

```
for ^10**6 {.say if $_*($_+2010)/($_ gcd 2010)**2==2014}

```

I can save another couple of characters by using `... && .say` instead of `.say if ...`, because I don't need a space on both sides of `&&` like I do for `if`.

```
for ^10**6 {$_*($_+2010)/($_ gcd 2010)**2==2014&&.say}

```

Since I did both of the previous "optimizations" I can use the statement modifier form of `for`, which means I can remove `{` and `}`.

```
$_*($_+2010)/($_ gcd 2010)**2==2014&&.say for ^10**6

```

I think that is as short as I can go without using a different algorithm.
> 2 votes

# Answer
# J, 26 bytes

```
   I.((*.=+.*4--)2010+])i.1e6
4 5092

```

Those damned 2-byte verbs... :)
> 2 votes

# Answer
# Dyalog APL, 29 characters

```
      a←⍳10        ⍝ the integers up to 10
      a
1 2 3 4 5 6 7 8 9 10
      2010+a       ⍝ corresponding integers at distance 2010
2011 2012 2013 2014 2015 2016 2017 2018 2019 2020
      a∨2010+a     ⍝ GCD-s between elements of a and 2010+a
1 2 3 2 5 6 1 2 3 10
      ⍝ All APL functions (e.g. + and ∨) are prefix-or-infix, right-associative,
      ⍝ and of the same precedence.
      a∧2010+a     ⍝ LCM-s
2011 2012 2013 4028 2015 2016 14119 8072 6057 2020
      ⍝ For which of them is the LCM 2014 times the GCD?
      (a∧2010+a)=2014×a∨2010+a
0 0 0 1 0 0 0 0 0 0
      ⍝ 0 means false, 1 means true
      ⍝ Filter the elements of "a" corresponding to the 1-s
      ((a∧2010+a)=2014×a∨2010+a) / a
4
      ⍝ Let's abstract this as a function by using curlies.
      ⍝ Omega (⍵) stands for the right argument.
      {((⍵∧2010+⍵)=2014×⍵∨2010+⍵) / ⍵} a
4
      ⍝ Up to a million instead of up to ten:
      {((⍵∧2010+⍵)=2014×⍵∨2010+⍵) / ⍵} ⍳1e6
4 5092
      ⍝ Hey, we can save a few characters by making 2010 the left argument, alpha (⍺)
      2010 {((⍵∧⍺+⍵)=2014×⍵∨⍺+⍵) / ⍵} ⍳1e6
4 5092
      ⍝ Remove a pair of parens by using the switch operator ⍨
      ⍝ An "operator" occurs to the right of a function and modifies its behaviour.
      ⍝ In this case A f⍨ B means the same as B f A
      ⍝ Left and right are swapped, hence "switch".
      2010 {⍵ /⍨ (⍵∧⍺+⍵)=2014×⍵∨⍺+⍵)} ⍳1e6
4 5092
      ⍝ That's 32 characters (modulo whitespace).  Not bad, but we can do better.
      ⍝ A "fork" is a sequence of 3 functions in isolation: f g h
      ⍝ It is evaluated as:  ⍺(f g h)⍵  ←→  (⍺ f ⍵)g(⍺ h ⍵)
      ⍝ If the first item is an array instead of a function: A f g  ←→  {A} f g
      ⍝ Forks are right-associative: f g h k l ←→ f g (h k l)
      2010 {⍵ /⍨ (⍺(⊢∧+)⍵)=2014×(⍺(⊢∨+)⍵)} ⍳1e6
4 5092
      ⍝ The "right tack" function (⊢) simply returns its right argument
      ⍝ Let's abuse forks a little further:
      2010 {⍵ /⍨ ⍺((⊢∧+)=(2014×(⊢∨+)))⍵} ⍳1e6
4 5092
      ⍝ ... and more
      2010 {⍺ (⊢(/⍨)((⊢∧+)=(2014×(⊢∨+)))) ⍵} ⍳1e6
4 5092
      ⍝ But {⍺ f ⍵} is equivalent to f
      2010 (⊢(/⍨)((⊢∧+)=(2014×(⊢∨+)))) ⍳1e6
4 5092
      ⍝ Note that now we are not mentioning ⍺ and ⍵ at all.
      ⍝ This is called "point-free style" or "tacit programming".
      ⍝ Removing some unnecessary parens and whitespace:
      2010(⊢(/⍨)(⊢∧+)=2014×⊢∨+)⍳1e6
4 5092
      ⍝ How many characters?
      ⍴'2010(⊢(/⍨)(⊢∧+)=2014×⊢∨+)⍳1e6'
29

```
> 1 votes

# Answer
# PARI/GP, 42 bytes

```
[n|n<-[1..8!],2014*gcd(n,t=n+2010)^2==n*t]

```

I feel that there is an extremely elegant solution using GP's `fordiv` construct but it couldn't compete with this solution for sheer brevity.
> 1 votes

# Answer
## Racket, 72 chars

```
(filter(λ(i)(=(/(*(+ i 2010)i)(expt(gcd(+ i 2010)i)2))2014))(range 1e6))

```
> 0 votes

# Answer
## Haskell, 52 chars

```
show [x|x<-[1..6^8],x*(x+2010)==2014*(gcd x 2010)^2]

```

Works in the Haskell interactive environment GHCi.
> 0 votes

# Answer
# Jelly, ~~20~~ 19 bytes

```
g²×⁽¥Æ=×
ȷ6ç+⁽¥µ$$Ƈ

```

Try it online!

The TIO link has been modified to only search up to \\$10^4\\$, as the outputs are both below that, in order to finish within 60 seconds on TIO.

And of course, the "cheaty method" is that, as \\$4\\$ and \\$5092\\$ are the only two integers (as proven by kennytm) for which this is true, this 5 byter works:

```
4,⁽Ñ[

```

Try it online!

## How it works

```
g²×⁽¥Æ=× - Helper link. Takes n on the left and n+2010 on the right
g        - gcd(n, n+2010)
 ²       - gcd(n, n+2010)²
   ⁽¥Æ   - Compressed integer; 2014
  ×      - 2014×gcd(n, n+2010)²
       × - n²+2010n
      =  - Are the two equal?

ȷ6ç+⁽¥µ$$Ƈ - Main link. Takes no input
ȷ6         - Yield 1000000
       $$Ƈ - Yield [1, 2, ..., 1000000] and keep those, i, for which the following is true:
    ⁽¥µ    -   Compressed integer; 2010
   +       -   i+2010
  ç        -   Call the helper link with i on the left and i+2010 on the right

```
> 0 votes

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


title: Simulate my keyboard wave light!

text:
# Question
Title: Simulate my keyboard wave light!
(The word frame in the following text does not mean an actual frame, it is used as a placeholder for an undefined time unit)

# The task

Imagine you have a keyboard layout with only letters like so:

```
q w e r t y u i o p
 a s d f g h j k l
  z x c v b n m

```

Whenever you press a key, for example `f`, the keyboard lights up the keys around it each frame like this (unordered, each line is a separate frame):

```
F
RTGVCD
YHBXSE
UJNWAZ
IKMQ
OL
P

```

As you can see, each frame lights up the keys around the ones that were lit previously, but not the ones that have already been lit up before.

After you have determined which keys need to be pressed each frame, you need to visualize them. For each frame, you print out the default keyboard layout (with all of the whitespace), but with the lit up keys uppercased. In our example:

```
q w e r t y u i o p
 a s d F g h j k l
  z x c v b n m

q w e R T y u i o p
 a s D f G h j k l
  z x C V b n m

q w E r t Y u i o p
 a S d f g H j k l
  z X c v B n m

q W e r t y U i o p
 A s d f g h J k l
  Z x c v b N m

Q w e r t y u I o p
 a s d f g h j K l
  z x c v b n M

q w e r t y u i O p
 a s d f g h j k L
  z x c v b n m

q w e r t y u i o P
 a s d f g h j k l
  z x c v b n m

```

# Rules

1. Input will be a single letter, you can choose whether it will be capitalized or not.
2. Output can be either:

a. An array of multiline strings representing each second of the visualized keyboard

b. A single multiline string with each frame of the visualized keyboard separated by at least one newline
3. You can output a trailing newline or/and the final keyboard visualization when no keys are lit anymore

# Test cases

```
Input: F
Output:
q w e r t y u i o p
 a s d F g h j k l
  z x c v b n m

q w e R T y u i o p
 a s D f G h j k l
  z x C V b n m

q w E r t Y u i o p
 a S d f g H j k l
  z X c v B n m

q W e r t y U i o p
 A s d f g h J k l
  Z x c v b N m

Q w e r t y u I o p
 a s d f g h j K l
  z x c v b n M

q w e r t y u i O p
 a s d f g h j k L
  z x c v b n m

q w e r t y u i o P
 a s d f g h j k l
  z x c v b n m

Input: Q
Output:

Q w e r t y u i o p
 a s d f g h j k l
  z x c v b n m

q W e r t y u i o p
 A s d f g h j k l
  z x c v b n m

q w E r t y u i o p
 a S d f g h j k l
  Z x c v b n m

q w e R t y u i o p
 a s D f g h j k l
  z X c v b n m

q w e r T y u i o p
 a s d F g h j k l
  z x C v b n m

q w e r t Y u i o p
 a s d f G h j k l
  z x c V b n m

q w e r t y U i o p
 a s d f g H j k l
  z x c v B n m

q w e r t y u I o p
 a s d f g h J k l
  z x c v b N m

q w e r t y u i O p
 a s d f g h j K l
  z x c v b n M

q w e r t y u i o P
 a s d f g h j k L
  z x c v b n m

Input: Z
Output:
q w e r t y u i o p
 a s d f g h j k l
  Z x c v b n m

q w e r t y u i o p
 A S d f g h j k l
  z X c v b n m

Q W E r t y u i o p
 a s D f g h j k l
  z x C v b n m

q w e R t y u i o p
 a s d F g h j k l
  z x c V b n m

q w e r T y u i o p
 a s d f G h j k l
  z x c v B n m

q w e r t Y u i o p
 a s d f g H j k l
  z x c v b N m

q w e r t y U i o p
 a s d f g h J k l
  z x c v b n M

q w e r t y u I o p
 a s d f g h j K l
  z x c v b n m

q w e r t y u i O p
 a s d f g h j k L
  z x c v b n m

q w e r t y u i o P
 a s d f g h j k l
  z x c v b n m

```

# Answer
# Haskell, 229 bytes

```
e=zip[0..]
x!y=abs$x-y
k=e["Q W E R T Y U I O P"," A S D F G H J K L","  Z X C V B N M"]
f c=filter(any(<"a").words)[unlines[[[z..]!!sum[32|z>'@',max(2*y!i)(y!i+x!j)/=d*2]|(x,z)<-e m]|(y,m)<-k]|(i,l)<-k,(j,h)<-e l,c==h,d<-[0..9]]

```

Try it online!

`f` takes an uppercase char argument and returns a list of multiline strings.

It loops over the keyboard layout looking for `(i,j)`, the position of the given character. When it finds it, for each `d<-[0..9]` it generates a string (`unlines[…]`) of the keyboard with all letters *not* `d` hex-steps away lowercased. It never takes longer than 10 steps for the wave to leave the keyboard, so this is OK. Finally, strings that don't contain any uppercase letters are filtered away from the result.

I calculate the hex distance between two points on the keyboard as: \\$ \max\left(2|y\_1-y\_2|, |x\_1-x\_2|+|y\_1-y\_2|\right)\\$. Here are some distances around a point under this metric:

```
   6666666                                 6 6 6 6
  654444456                               6 4 4 4 6
 65432223456                             6 4 2 2 4 6
6543210123456  --> on staggered grid:   6 4 2 0 2 4 6
 65432223456                             6 4 2 2 4 6
  654444456                               6 4 4 4 6
   6666666                                 6 6 6 6

```
> 9 votes

# Answer
# Charcoal, 82 bytes

```
≔⪪”&±=Ｋ≕⦃Vj@η⟲.w\`o:7➙1”¶υ≔⊟Φυ№ιθηΦＥχＥυ⁺× μ⪫⭆λ⎇⁼ι⌈↔⊟Ｅ⟦⟦⁻μ⌕υη⁻ξ⌕ηθ⟧⟧⊞ＯπΣπ↥νν ⊙ι⊙λ№αν

```

Try it online! Link is to verbose version of code. Takes input in lower case. Explanation:

```
≔⪪”&±=Ｋ≕⦃Vj@η⟲.w\`o:7➙1”¶υ

```

Get the list `qwertyuiop`, `asdfghjkl`, `zxcvbnm` by splitting a compressed string.

```
≔⊟Φυ№ιθη

```

Find the element of the above list that contains the input.

```
Ｅχ

```

Create a list of lists corresponding to each step away from the input on the staggered grid from 0 to 9.

```
Ｅυ⁺× μ⪫⭆λ⎇⁼ι⌈↔⊟Ｅ⟦⟦⁻μ⌕υη⁻ξ⌕ηθ⟧⟧⊞ＯπΣπ↥νν

```

Uppercase the letters that are the desired distance from the input on the staggered grid, then stagger the result by prefixing each line with an increasing number of spaces and double-spacing the letters.

```
Φ...⊙ι⊙λ№αν

```

Only print those lists that contain an uppercase letter.

The formula I'm using for distance is the maximum of \\$|x\_2-x\_1|\\$, \\$|y\_2-y\_1|\\$ and \\$|x\_2-x\_1+y\_2-y\_1|\\$ their sum, where \\$y\\$ is the (0-indexed) row counting down and \\$x\\$ is the (skewed) column:

```
0 1 2 3 4 5 6 7 8 9
 0 1 2 3 4 5 6 7 8
  0 1 2 3 4 5 6

```
> 7 votes

# Answer
# 05AB1E, ~~59~~ ~~57~~ 50 bytes

Thanks to Kevin Cruijssen for -3 bytes!

Input is in lowercase, the program prints the keyboards separated by empty lines. Outputs the final dark keyboard for some keys.

Uses the distance metric from Lynn's answer.

```
žVðæ.ιSðý©Ik19‰¸Þ2Ý18Ýâαε¬sO;‚à}>ZFD®sÅÏu}19ô»,¶?<

```

Try it online!

**Commented**:

```
                 # keyboard creation
žV               # push ["qwertyuiop", "asdfghjkl", "zxcvbnm"]
  ð              # push a space
   æ             # push the powerset ["", " "]
    .ι           # interleave both lists
      S          # split into a list of characters
       δý        # join with spaces
         ©       # store this value in the register

I                # push the input
 k               # the index of the input in the keyboard string
  19‰            # divmod by 19 to get [y, x]-coordinates
     ¸Þ          # cycle this value forever
       2Ý        # push [0..2]
         18Ý     # push [0..18]
            â    # cartesian product to get a list of all coordinates
             α   # take the element-wise difference [dy, dx] for each coord

                 # apply distance metric
ε      }         # map over the absolute differences:
 ¬               #   get the first element dy
  s              #   swap back to [dy, dx]
   O             #   sum it
    ;            #   halve it
     ‚           #   pair into a list [dy, (dy+dx)/2]
      à          #   take the maximum
        >        # increment every value
                 # so that the input position has value 1 (only truthy value)

                 # generate the outputs
Z                # take the maximum of the distances
 F               # iterate that many times:
  D              #   duplicate the distance list
   ®             #   push the keyboard string
    s            #   swap to the distance list
     ÅÏ }        #   apply where truthy (==1)
       u         #     uppercase
         19ô     #   split into groups of 19
            »    #   join by newlines
             ,   #   print
              ¶? #   print a newline
                <#   decrement distance list

```
> 2 votes

# Answer
# Jelly, 64 bytes

```
“¤Äı’b3’s2
+Ɱ¢ẎfØqŒṪ¤Q
ḢØqœiWÇƬḟ"ṖẎ$Ƥ$LƇœịØqżŒu$µyⱮØqK€2Żẋ@⁶¤;")

```

A monadic Link accepting a list of 1 character which yields a list of keyboards, each keyboard being a list of lists of characters (including the spacing given in the examples).

**Try it online!** (Footer joins the resulting keyboards with newline characters and joins the result with pairs of newline characters to display like the examples.)
> 0 votes

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


title: Write a Number as a Fibonacci Sum

text:
# Question
Title: Write a Number as a Fibonacci Sum
Let us define the Fibonacci sequence as

```
F(1) = 1

F(2) = 2

F(n) = F(n - 2) + F(n - 1)

```

So we have the infinite sequence `1,2,3,5,8,13,`... It is well known that any positive integer can be written as a sum of some Fibonacci numbers. The only caveat is that this summation might not be unique. There is always at least one way to write a number as a sum of Fibonacci numbers but there may be many many more.

Your challenge is to write a complete program which using stdin takes in a positive integer between one and one million inclusive, and then outputs using stdout all possible summations of Fibonacci numbers which sum up to the input. In a summation, the Fibonacci numbers must not repeat and that includes the number `1`. In any summation, if `1` is present, it must be present only once because in my definition of the sequence above `1` appears only once. Summations with only term are valid so if the input number is a Fibonacci number itself, then the number itself is a valid summation and must be printed. If multiple sums, then between any two sums there must be a blank line to easily distinguished between them.

Here are some samples.

```
./myfib 1
1

```

There is only one such sum and it has only term so that's all that is printed.

```
./myfib 2
2

```

Note here that `1+1` is not a valid sum because `1` repeats.

```
./myfib 3
1+2

3

```

Two sums and they are both printed with a blank line in between.

```
./myfib 10
2+8

2+3+5

./myfib 100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55

```

True code-golf. The shortest code in any language wins. Please post your code with some test cases (besides the one I gave above). In the case of ties, I pick the one with the highest upvotes after waiting at least for two weeks and probably longer. So the community please feel free to upvote any solutions you like. The cleverness/beauty of the code matters much more than who posts first.

Happy coding!

# Answer
### GolfScript, 54 characters

```
~1.{3$)<}{.@+}/<[[]]{{+}+1$%+}@/\{~)+{+}*!}+,{'+'*n.}/

```

Test it online or have a look at the examples:

```
> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55

```
> 9 votes

# Answer
# Ruby, ~~118~~ 114 (array output) or ~~138~~ 134 (correct output)

```
i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
p (1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}

```

Sample run:

```
c:\a\ruby>fibadd
100
[[3, 8, 89], [1, 2, 8, 89], [3, 8, 34, 55], [1, 2, 3, 5, 89], [1, 2, 8, 34, 55], [3, 8, 13, 21, 55], [1, 2, 3, 5, 34, 55], [1, 2, 8, 13, 21, 55], [1, 2, 3, 5, 13, 21, 55]]

```

Change `gets` to `$*[0]` if you want command line arguments (`>fibadd 100`), +1 character though.

With the correct output:

```
i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
$><<(1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}.map{|o|o*?+}*'

'

```

Sample runs:

```
c:\a\ruby>fibadd
100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55
c:\a\ruby>fibadd
1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610
c:\a\ruby>obfcaps
12804
2+5+21+233+1597+10946

2+5+8+13+233+1597+10946

2+5+21+89+144+1597+10946

2+5+21+233+610+987+10946

2+5+21+233+1597+4181+6765

2+5+8+13+89+144+1597+10946

2+5+8+13+233+610+987+10946

2+5+8+13+233+1597+4181+6765

2+5+21+34+55+144+1597+10946

2+5+21+89+144+610+987+10946

2+5+21+89+144+1597+4181+6765

2+5+21+233+610+987+4181+6765

2+5+8+13+34+55+144+1597+10946

2+5+8+13+89+144+610+987+10946

2+5+8+13+89+144+1597+4181+6765

2+5+8+13+233+610+987+4181+6765

2+5+21+34+55+144+610+987+10946

2+5+21+34+55+144+1597+4181+6765

2+5+21+89+144+233+377+987+10946

2+5+21+89+144+610+987+4181+6765

2+5+21+233+610+987+1597+2584+6765

2+5+8+13+34+55+144+610+987+10946

2+5+8+13+34+55+144+1597+4181+6765

2+5+8+13+89+144+233+377+987+10946

2+5+8+13+89+144+610+987+4181+6765

2+5+8+13+233+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+10946

2+5+21+34+55+144+610+987+4181+6765

2+5+21+89+144+233+377+987+4181+6765

2+5+21+89+144+610+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+10946

2+5+8+13+34+55+144+610+987+4181+6765

2+5+8+13+89+144+233+377+987+4181+6765

2+5+8+13+89+144+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+4181+6765

2+5+21+34+55+144+610+987+1597+2584+6765

2+5+21+89+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+4181+6765

2+5+8+13+34+55+144+610+987+1597+2584+6765

2+5+8+13+89+144+233+377+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+1597+2584+6765

```

That last one (12804) only took about 3 seconds!
> 4 votes

# Answer
# Mathematica, ~~89~~ 85 chars

Shortened to 85 chars thanks to David Carraher.

```
i=Input[];#~Row~"+"&/@Select[If[#>i,Subsets@{##},#0[#+#2,##]]&[2,1],Tr@#==i&]//Column

```

Mathematica has a built-in function `Fibonacci`, but I don't want to use it.
> 4 votes

# Answer
**Scala, 171**

```
def f(h:Int,n:Int):Stream[Int]=h#::f(n,h+n)
val x=readInt;(1 to x).flatMap(y=>f(1,2).takeWhile(_<=x).combinations(y).filter(_.sum==x)).foreach(z=>println(z.mkString("+")))

```
> 3 votes

# Answer
**Python ~~206~~ 181 characters**

```
import itertools as a
i,j,v,y=1,2,[],input()
while i<1000000:v,i,j=v+[i],j,i+j
for t in range(len(v)+1):
 for s in a.combinations(v,t):
  if sum(s)==y:print "+".join(map(str,s))+"\n"

```

Sample Run:

```
25
1+3+21

1+3+8+13

1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610

```
> 2 votes

# Answer
## C#, 376 bytes

```
class A{IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}static void Main(){new A().C(int.Parse(Console.ReadLine()));}}

```

Ungolfed:

```
class A
{
    IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}
    void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}
    static void Main(){new A().C(int.Parse(Console.ReadLine()));}
}

```

The method `B` returns an `IEnumerable` that represents the entire (infinite) Fibonacci set. The second method, given a number `n`, looks at the first `n` Fibonacci numbers (huge overkill here), finds all possible subsets (the power set), and then filters down to subsets whose sum is exactly `n`, and then prints.
> 2 votes

# Answer
## APL (75)

```
I←⎕⋄{⎕←⎕TC[2],1↓,'+',⍪⍵}¨S/⍨I=+/¨S←/∘F¨↓⍉(N⍴2)⊤⍳2*N←⍴F←{⍵,+/¯2↑⍵}⍣{I<⊃⌽⍺}⍳2

```

Less competitive than I'd like, mostly because of the output format.

Output:

```
⎕:
      100

 3 + 8 + 89

 3 + 8 + 34 + 55

 3 + 8 + 13 + 21 + 55

 1 + 2 + 8 + 89

 1 + 2 + 8 + 34 + 55

 1 + 2 + 8 + 13 + 21 + 55

 1 + 2 + 3 + 5 + 89

 1 + 2 + 3 + 5 + 34 + 55

 1 + 2 + 3 + 5 + 13 + 21 + 55

```

Explanation:

* `I←⎕`: read input, store in `I`.
* `⍳2`: starting with the list `1 2`,
* `{⍵,+/¯2↑⍵}`: add the sum of the last two elements to the list,
* `⍣{I<⊃⌽⍺}`: until `I` is smaller than the last element of the list.
* `F←`: store in `F` (these are the fibonacci numbers from `1` to `I`).
* `N←⍴F`: store the amount of fibonacci numbers in `N`.
* `↓⍉(N⍴2)⊤⍳2*N`: get the numbers from `1` to `2^N`, as bits.
* `S←/∘F¨`: use each of these as a bitmask on `F`, store in `S`.
* `I=+/¨S`: for each sub-list in `S`, see if the sum of it is equal to `I`.
* `S/⍨`: select these from `S`. (Now we have all lists of fibonacci numbers that sum to `I`.)
* `{`...: for each of these:
    + `,'+',⍪⍵`: add a `+` in front of each number,
    + `1↓`: take the first `+` back off,
    + `⎕TC[2]`: add an extra newline,
    + `⎕←`: and output.
> 1 votes

# Answer
## Haskell - 127

After many iterations I ended up with the following code:

```
f=1:scanl(+)2f
main=getLine>>=putStr.a f "".read
a(f:g)s n|n==f=s++show f++"\n\n"|n<f=""|n>f=a g(s++show f++"+")(n-f)++a g s n

```

I could have saved maybe one character by cheating and adding an extra "0+" in front of every output line.

I want to share another version (length 143) I came up with while trying to golf the previous solution. I've never abused operators and tuples quite this much before:

```
f=1:scanl(+)2f
main=getLine>>=(\x->putStr$f€("",read x))
o%p=o++show p;(f:g)€t@(s,n)|n==f=s%f++"\n\n"|n<f=""|n>f=g€(s%f++"+",n-f)++g€t

```

Test cases, 256:

```
256
2+3+5+13+34+55+144

2+3+5+13+89+144

2+3+5+13+233

2+8+13+34+55+144

2+8+13+89+144

2+8+13+233

2+21+34+55+144

2+21+89+144

2+21+233

```

and 1000:

```
1000
2+3+8+21+34+89+233+610

2+3+8+55+89+233+610

2+3+8+144+233+610

2+3+8+377+610

2+3+8+987

5+8+21+34+89+233+610

5+8+55+89+233+610

5+8+144+233+610

5+8+377+610

5+8+987

13+21+34+89+233+610

13+55+89+233+610

13+144+233+610

13+377+610

13+987

```

Some efficiency data since someone had this stuff:

```
% echo "12804" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  0.09s user 0.00s system 96% cpu 0.100 total
% echo "128040" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  2.60s user 0.01s system 99% cpu 2.609 total

```
> 1 votes

# Answer
# CJam, ~~42~~ 40 bytes

*-2 bytes by converting each list from base 1 to calculate its sum instead of using `:+`. (This saves no bytes by itself, but this method works on the empty set, so it no longer needs to be discarded from the list of lists.)*

```
XY{_2$+}qi:T*]La\{1$f++}/{1bT=},{'+*}%N*

```

Try it online!

This takes a long time to calculate for large numbers because it generates `input + 2` Fibonacci numbers (to ensure that every number less than or equal to the input is included)...but hey, it saves 4 bytes over using a proper while loop.
> 1 votes

# Answer
# 05AB1E, 19 bytes (Non-competing)

```
ÅFævy©O¹Qi®'+ý}})ê»

```

Try it online!

Calculates all possible sums for any given `n`. Example output for 1000:

```
1+1+3+8+144+233+610
1+1+3+8+21+34+89+233+610
1+1+3+8+377+610
1+1+3+8+55+89+233+610
1+1+3+8+987
13+144+233+610
13+21+34+89+233+610
13+377+610
13+55+89+233+610
13+987
2+3+8+144+233+610
2+3+8+21+34+89+233+610
2+3+8+377+610
2+3+8+55+89+233+610
2+3+8+987
5+8+144+233+610
5+8+21+34+89+233+610
5+8+377+610
5+8+55+89+233+610
5+8+987

```
> 0 votes

# Answer
# Husk, <sup>~~22~~</sup> 20 bytes

```
ṁȯeøJ'+msufo=¹ΣṖt↑İf

```

Try it online!

-2 bytes with an empty list trick.

## Explanation

```
moJ'+msufo=¹ΣṖt↑İf
               ↑İf Take input number of fibonacci numbers
              t    remove first 1
             Ṗ     get it's powerset
        fo         filter the sublists by the following:
          =¹Σ      sum equals input?
       u           uniquify it
mo                 map each sublist to
     ms            it's elements as strings
  J'+              Joined by '+'

```
> 0 votes

# Answer
# Japt, 21 bytes

```
õ!gM Åà f@¶XxÃ®q+ÃqR²

```

Try it
> 0 votes

---
Tags: code-golf, fibonacci
---


title: Progressing Two's

text:
# Question
Title: Progressing Two's
Given an positive integer `n` (including 0 if you decide to support it), output all numbers in the *generated* sequence up to the index `n`. For the current test cases of the current challenge numbers are one-indexed. Feel free to submit 0-indexed answers though.

## Base sequence

We start from this sequence (**NOT**, but quite similar to, A160242):

```
1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, ...

```

This sequence should be more understandable after formatting:

```
1,       2,       1,
1,    2, 2, 2,    1,
1, 2, 2, 2, 2, 2, 1,
and so on ...

```

However, our point is not to output this sequence. See the below procedure.

## Adding the sequence

Here's an example of adding the sequence. Here, our sequence starts with 0:

```
We collect all intermediate results into the sequence.
  The sequence
    |     Output sequence: [0]
    v
0 + 1 = 1 Output sequence: [0, 1]
1 + 2 = 3 Output sequence: [0, 1, 3]
3 + 1 = 4 Output sequence: [0, 1, 3, 4]
4 + 1 = 5 Output sequence: [0, 1, 3, 4, 5]
...

Our generated sequence is therefore

0, 1, 3, 4, ...

```

## Test cases

Here is a sample program outputting the sequence up to the input.

```
3 -> [0, 1, 3]
10 -> [0, 1, 3, 4, 5, 7, 9, 11, 12, 13]

```

# Answer
# 05AB1E, ~~9~~ 7 bytes

```
ÝDtï-ü+

```

Port of *@Bubbler*'s top APL answer, which uses the same formula as *@xnor*'s Python answer:
$$f(n) = \sum\_{k \in \\{n,n+1\\}}\left({k-\lfloor \sqrt k\rfloor}\right)$$

-2 bytes thanks to *@Grimmy*.

Try it online.

**Explanation:**

```
Ý        # Push a list in the range [0, (implicit) input-integer]
 D       # Duplicate this list
  t      # Take the square-root of each value
   ï     # Cast it to an integer to floor it
    -    # Subtract the values at the same positions from one another
     ü   # For each overlapping pair:
      +  #  Add them together
         # (after which the result is output implicitly)

```

---

Implementing the steps described in the challenge description would be **13 bytes** instead:

```
2∞и1δš€û˜.¥I£

```

Try it online.

Or `2∞и1δš€û` could alternatively be `ÅÉÅ21δ.ø`.

Try it online.

**Explanation:**

```
 ∞             # Push an infinite positive list: [1,2,3,...]
2 и            # Repeat 2 that many times as list: [[2],[2,2],[2,2,2],...]
    δ          # For each inner list:
   1 š         #  Prepend a leading 1: [[1,2],[1,2,2],[1,2,2,2],...]
      €        # For each inner list:
       û       #  Palindromize it: [[1,2,1],[1,2,2,2,1],[1,2,2,2,2,2,1],...]
        ˜      # Flatten the list of 1s and 2s: [1,2,1,1,2,2,2,1,1,2,2,2,2,2,1,...]
         .¥    # Undelta it (cumulative sum with 0 automatically prepended):
               #  [0,1,3,4,5,7,9,11,12,13,15,17,19,21,23,24,25,...]
           I£  # Leave the first input amount of items from this infinite list
               # (after which the result is output implicitly)

ÅÉ             # Push a list of odd numbers below or equal to the (implicit) input
               #  i.e. 6 → [1,3,5]
  Å2           # Repeat a list of 2s for each inner value: [[2],[2,2,2],[2,2,2,2,2]]
     δ         # For each inner list:
    1 .ø       #  Surround it with 1s: [[1,2,1],[1,2,2,2,1],[1,2,2,2,2,2,1]]
               # (The rest is the same as above)

```
> 3 votes

# Answer
# Python 2, 52 bytes

```
n=p=0
exec"n+=1;r=n-n**.5//1;print p+r;p=r;"*input()

```

Try it online!

**54 bytes**

```
lambda N:[n-~n-n**.5//1-(n+1)**.5//1for n in range(N)]

```

Try it online!

It's a formula!

$$f(n) = 2n+1 - \lfloor \sqrt n\rfloor - \lfloor \sqrt {n+1} \rfloor$$

This can also be split up as

$$f(n) = \sum\_{k \in \\{n,n+1\\}}\left({k-\lfloor \sqrt k\rfloor}\right)$$

Note that \\$k-\lfloor \sqrt k\rfloor\\$ is the number of non-squares from \\$1\\$ to \\$k\\$ inclusive.
> 8 votes

# Answer
# APL (Dyalog Extended), ~~14~~ 12 bytes

```
0,2+/⍳-⌊∘√∘⍳

```

Try it online!

Uses xnor's formula of

$$ f(n) = \sum\_{k \in \\{n,n+1\\}}\left({k-\lfloor \sqrt k\rfloor}\right) $$

### How it works

```
0,2+/⍳-⌊∘√∘⍳
     ⍳-       ⍝ 1..n minus...
       ⌊∘√∘⍳  ⍝ floor(sqrt(1..n))
  2+/         ⍝ Add two consecutive pairs
              ⍝ giving first n items of the sequence except leading 0
0,            ⍝ Prepend the leading 0

```

---

# APL (Dyalog Extended), 14 bytes

```
⊢↑2(∧+/,2××/)⍳

```

Try it online!

Based on the observation that the sequence is the union of all odd numbers and the numbers in the form of \\$2n(n+1), n \ge 0\\$. Uses `⎕IO←0`.

### How it works

```
⊢↑2(∧+/,2××/)⍳  ⍝ Input: positive integer n
             ⍳  ⍝ Generate 0..n-1
  2(      ×/)   ⍝ Pairwise product (0×1, 1×2, ..., (n-2)×(n-1))
        2×      ⍝ Double it
     +/,        ⍝ Concat with pairwise sum (0+1, 1+2, ..., (n-2)+(n-1))
    ∧           ⍝ Ascending sort the 2(n-1) numbers in total
⊢↑              ⍝ Take the first n numbers
                ⍝ For n=1, "overtake" from zero elements, giving single 0

```
> 6 votes

# Answer
# Haskell, 42 bytes

```
(`take`q 4)
q k=0:[1,3..k]++map(k+)(q$k+4)

```

Try it online!

Uses a version of Bubbler's observation that the sequence alternates runs of consecutive odd numbers with an even number directly in between.

---

# Haskell, 43 bytes

```
(`take`scanl(+)0(q[2]))
q r=1:r++1:q(2:2:r)

```

Try it online!

Generates an infinite list of 1's and 2's, take the cumulative sums, and truncates to the input length.
> 5 votes

# Answer
# Jelly, 8 bytes

```
R_Æ½$+ƝŻ

```

Try it online!

-5 bytes by porting xnor's formula (thanks Bubbler!)

-1 byte thanks to Nick Kennedy

# Explanation

Uses xnor's formula of:

$$f(n) = \sum\_{k \in \\{n,n+1\\}}\left({k-\lfloor \sqrt k\rfloor}\right)$$

```
R_Æ½$+ƝŻ    Main Link
R           range
 _   $      subtract
  Æ½                 square root floored (of each element)
     +Ɲ     add adjacent pairs together
       Ż    prepend 0

```

Without xnor's formula, I have 10 bytes

# Jelly, 10 bytes

```
RÆ²Ẹ$Ɲ¬‘ÄŻ

```

Try it online!

(range; for each pair of adjacent elements, check if either of them is square; logical NOT that and add one (gets the original 1,2 sequence), cumulative sum, prepend 0)
> 2 votes

# Answer
# Perl 5 `-MList::Util=sum -n`, 39 bytes

Shoutout to @xnor for the formula. This is essentially a port of his Python answer.

```
map{say$a+($n=$_-int$_**.5);$a=$n}1..$_

```

Try it online!
> 2 votes

# Answer
# Bash \+ GNU utilities, ~~33~~ 29 bytes

```
seq -f %0.fddv-r1-dv-+p $1|dc

```

Try it online!

This is another solution using @xnor's nice formula.
> 2 votes

# Answer
# JavaScript (ES7), 40 bytes

This is using the closed-form formula described below.

But because we're asked to output the \\$n\\$ first terms of the sequence, we need 19 bytes of wrapping code. :'-(

```
f=n=>n?[...f(n-1),(n-=n**.5)*2|n%1>0]:[]

```

Try it online!

### 21 bytes (n-th term, 1-indexed)

```
n=>(n-=n**.5)*2|n%1>0

```

Try it online!

Given \\$n\ge0\\$, we compute:

$$d(n)=2\cdot\lfloor n-\sqrt{n}\rfloor\\ f(n)=\cases{ d(n)&\text{if $n$ is a square}\\ d(n)+1&\text{otherwise} }$$

The JS implementation uses a bitwise OR which implicitly floors \\$n-\sqrt{n}\\$ *after* it has been multiplied by \\$2\\$. But this leads to the same result.
> 2 votes

# Answer
# 05AB1E, 9 bytes

```
ENÅ²_©O=®

```

Try it online!

```
E           # loop for N from 1 to input:
 NÅ²        #  is N a square?
    _       #  logical not (0 if N is a square, 1 if not)
     ©      #  save in the register without popping
      O     #  sum all numbers on the stack
       =    #  print without popping
        ®   #  push the content of the register

```
> 1 votes

# Answer
# Python 3, 93 bytes

```
f=lambda n,x=0:(n-x)*[1]and[sum([j for i in range(1,n,2)for j in[1]+[2]*i+[1]][:x])]+f(n,x+1)

```

Try it online!

*-21 bytes thanks to @Bubbler*
> 0 votes

# Answer
# Python 2, 71 bytes

```
f=lambda n,k=0,w=3:n*[n]and[0]+[x-~(k>1)for x in f(n-1,~-k%w,w+2*0**k)]

```

Try it online!
> 0 votes

# Answer
# Ruby, ~~52~~ 50 bytes

```
->n,*w{n.times{|x|w+=[x,x*x,x*x];p w.sort[x+1]+x}}

```

Try it online!

### How:

The difference between n and f(n) shows an interesting pattern:

```
n   f   f-n
----------
0   0   0
1   1   0
2   3   1
3   4   1
4   5   1
5   7   2
6   9   3
7   11  4
8   12  4
9   13  4
10  15  5
11  17  6
12  19  7
13  21  8
14  23  9
15  24  9
16  25  9
17  27  10
18  29  11
19  31  12

```

In the rightmost sequence, every non-square number occurs only once, and every square number appears three times (except 0 which occurs only twice). I can build the required sequence as the sum of n and (f-n).
> 0 votes

# Answer
# Charcoal, 17 bytes

```
ＩＥＥＮ…±⊕ι⊕ιＬ⁻↔ιＸι²

```

Try it online! Link is to verbose version of code. Based on @xnor's formula. Explanation:

```
   Ｎ                Input as a number `m`
  Ｅ                 Map over implicit range `0`..`m-1`
       ι ι          Current index `n`
      ⊕ ⊕           Incremented (i.e. `1`..`m`)
     ±              Negated
    …               Exclusive range (i.e. `-n` .. `n-1`)
 Ｅ                  Map over list of ranges
             ι ι    Current range
              Ｘ ²   Squares of values
            ↔       Absolute values
           ⁻        Remove the squares
          Ｌ         Take the length
Ｉ                   Cast to string
                    Implicitly print

```
> 0 votes

# Answer
# C (gcc) `-lm`, ~~72~~ \\$\cdots\\$ ~~61~~ 60 bytes

Saved a byte thanks to ceilingcat!!!

```
s;i;f(n){for(s=i=0;i<n;)printf("%d ",i-~i-s-(s=sqrt(++i)));}

```

Try it online!

Uses xnor's formula.
> 0 votes

# Answer
# C (gcc), 81 bytes

```
r,c,i;f(n){for(r=c=0;~n;c++)for(i=++c;i--+2&&n--;r+=c+~i&&i+2)printf("%d ",r++);}

```

Some magic hackery used.

*-4 bytes thanks to ceilingcat!*

Try it online!
> 0 votes

# Answer
# Jelly, 7 bytes

```
Ż_Æ½$+Ɲ

```

A monadic Link accepting a positive integer, `n`, which yields a list of the first `n` entries.

**Try it online!**

### How?

Application of xnor's pair-wise addition formula \\$f(n) = \sum\_{k \in \\{n,n+1\\}}\left({k-\lfloor \sqrt k\rfloor}\right)\\$

```
Ż_Æ½$+Ɲ - integer, n                       e.g. 10
Ż       - zero range                            [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    $   - last two links as a monad:
  Æ½    -   integer square-root (vectorises)    [0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3]
 _      -   subtract (vectorises)               [0, 0, 1, 2, 2, 3, 4, 5, 6, 6, 7]
      Ɲ - for neighbours:
     +  -   add                                  [0, 1, 3, 4, 5, 7, 9, 11,12,13]

```
> 0 votes

# Answer
# Husk, 10 bytes

```
ΘẊ+mṠ-o⌊√ḣ

```

Try it online!
> 0 votes

# Answer
# Japt, 8 bytes

Another port of xnor's formula.

```
ôÈ-¬fÃä+

```

Try it

```
ôÈ-¬fÃä+     :Implicit input of integer
ô            :Range [0,input]
 È-          :Map & subtract
   ¬         :  Square root
    f        :  Floored
     Ã       :End map
      ä+     :Consecutive pairs reduced by addition

```
> 0 votes

---
Tags: code-golf, sequence
---


# Question
Title: Find the nth Fibonnaci Prime, in the shortest code
The challenge is rather simple:

1. Take a positive whole number \\$n\\$ as input.
2. Output the \\$n\\$th Fibonacci prime number, i.e. the \\$n\\$th Fibonacci number that is also prime.

Input can be as an parameter to a function (and the output will be the return value), or can be taken from the command line (and outputted there).

*Note: Using built in prime checking functions or Fibonacci series generators is not allowed.*

The first 10 Fibonacci primes are

```
[2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437]

```

Shortest code wins. Good luck!

# Answer
# Ruby, 55

```
f=->n,a=1,b=2{n<1?a:f[n-(2..b).find{|f|b%f<1}/b,b,a+b]}

```

Calls itself recursively, keeping track of the last two numbers in the Fibonacci sequence in `a` and `b`, and how many primes it's seen so far with `n`. `n` gets decremented when the smallest factor greater than 1 of `b`, divided by `b` and rounded down to the nearest integer, is 1 rather than 0, which happens only for prime `b`. When it's seen all the primes it's supposed to, it prints `a`, which is the most recent `b` tested for primality.
> 2 votes

# Answer
# C, 66

`f(n,a,b){int i=2;while(a%i&&i++<a);return(n-=i==a)?f(n,b,a+b):a;}`
> 4 votes

# Answer
## C, 85, 81, 76

```
f(n){int i=1,j=0,k;for(;n;n-=k==i)for(j=i-j,i+=j,k=2;i%k&&k++<i;);return i;}

```
* borrowed code style of simplified prime number check from @Gautam
* self contained C function (no globals)

Testing:

```
main(int n,char**v){printf("%d\n",f(atoi(v[1])));}

./a.out 10
433494437

./a.out 4
13

```
> 3 votes

# Answer
# Mathematica, 59 or 63 bytes

```
(a=b=1;Do[While[{a,b}={b,a+b};Length@Divisors@b>2],{#}];b)&
(a=b=1;Do[While[{a,b}={b,a+b};b~Mod~Range@b~Count~0>2],{#}];b)&

```

These are unnamed functions which take `n` as their input and return the correct Fibonacci prime. The shorter version uses `Divisors`. I'm not entirely sure whether this is allowed, but the other Mathematica answer even uses `FactorInteger`.

The second one doesn't use any factorisation related functions at all, but instead counts the number of integers smaller than `n` which produce `0` in a modulo operation. Even this version beats all valid submissions, but I'm sure just posting this answer will cause some people to provide competitive answers in GolfScript, APL or J. ;)
> 2 votes

# Answer
# Ruby, ~~94 68~~ 67

```
n=->j{a=b=1
while j>0
a,b=b,a+b
(2...b).all?{|m|b%m>0}&&j-=1
end
b}

```

# Clojure, 112

Ungolfed:

```
(defn nk [n]
  (nth
    (filter
      (fn[x] (every? #(> (rem x %) 0) (range 2 x)))    ; checks if number is prime
      ((fn z[a b] (lazy-seq (cons a (z b (+ a b))))) 1 2)) ; Fib seq starting from [1, 2]
    n)) ; get nth number

```

Golf: `(defn q[n](nth(filter(fn[x](every? #(>(rem x %)0)(range 2 x)))((fn z[a b](lazy-seq(cons a(z b(+ a b)))))2 3))n))`
> 1 votes

# Answer
# Mathematica 147 143 141 chars

```
f@0 = 0; f@1 = 1; f@n_ := f[n - 1] + f[n - 2]
q@1 = False; q@n_ := FactorInteger@n~MatchQ~{{_, 1}}
p = {}; k = 1; While[Length@p < n, If[q@f@k, p~AppendTo~f[k]]; k++];p[[-1]]

```

`f` is the recursive definition of Fibonacci number.

`q` detects primes.

`k` is a Fibonacci prime iff `q@f@k` is True.

For `n`=10, output is `433494437`.
> 1 votes

# Answer
# Haskell 108

```
p=2 : s [3,5..]  where
    s (p:xs) = p : s [x|x<-xs,rem x p /= 0]
f=0:1:(zipWith (+) f$tail f)
fp=intersect p f

```

To get `n`th number call it `fp !! n`.

EDIT: Sic. Wrong answer, I fix it.
> 1 votes

# Answer
# Husk, 15 bytes

```
!fȯ=2LḊ¡oΣ↑_2ḋ3

```

Try it online!
> 1 votes

# Answer
## Groovy: 105 (134 with whitespaces)

`b` is the fibonacci function.

the closure inside the if is the prime check function. **Update: a small fix on it**

`r` is the prime fibonacci number.

```
r={ n->
  c=k=0
  while(1) {
    b={a->a<2?a:b(a-1)+b(a-2)}
    f=b k++
    if({z->z<3?:(2..<z).every{z%it}}(f)&&c++==n)return f
  }
}

```

Test cases:

```
assert r(0) == 0
assert r(1) == 1
assert r(2) == 1
assert r(3) == 2
assert r(4) == 3
assert r(5) == 5
assert r(6) == 13
assert r(7) == 89
assert r(8) == 233
assert r(9) == 1597

```

A readable version:

```
def fib(n) {
  n < 2 ? n : fib(n-1) + fib(n-2)
}
def prime(n) {
  n < 2 ?: (2..<n).every { n % it }
}
def primeFib(n) {
  primes = inc = 0
  while( 1 ) {
    f = fib inc++
    if (prime( f ) && primes++ == n) return f
  }
}

```
> 0 votes

# Answer
# C, 105 (with spaces)

### fibonacci implementation using dynamic programming:

```
long f(int n){int i;long b2=0,b1=1,n;if(n)return 0;for(i=2;i<n;i++){n=b1+b2;b2=b1;b1=n;}return b1+b2;}

```

Readable code:

```
long f(int n)
{
  int i;
  long back2 = 0, back1 = 1;
  long next;

  if ( n == 0 ) return 0;

  for ( i=2; i<n; i++ )
  {
    next  = back1 + back2;
    back2 = back1;
    back1 = next;
  }

  return back1 + back2;
}

```
> 0 votes

# Answer
# Pyth \- 29 bytes

Loops Fibonacci until array is length n but only adds to array if prime.

```
J2K1W<lYQAJK,+KJJI!tPK~Y]K;eY

```

Kind of slow, but reached n=10 in ~15 seconds. Can probably be golfed more.

```
J2              J=2
K1              K=1
W        <lYQ   While length of array<input
 AJK,+KJJ       J,K=K+J,J
 I!tPK          If K prime(not builtin prime function, uses prime factorization)
  ~Y]K          append K to Y
;               End loop so next is printed
eY              last element of Y

```
Disclaimer: Pyth is newer than this challenge, so not competing.
> 0 votes

# Answer
# Jelly, 15 bytes

```
0+⁸¡1
ÇÆḍ=1µ#ṪÇ

```

Try it online!

The version that uses builtins is 8 bytes. This is a direct translation of that answer, but with the builtins replaced. This takes input

## How it works

```
0+⁸¡1 - Helper link. Takes k on the left
0     - Set 0 as the left argument
    1 - Set 1 as the right argument
  ⁸¡  - Repeat k times, updating the left and right arguments each time:
 +    -   Add
        This yields the kth Fibonacci number

ÇÆḍ=1µ#ṪÇ - Main link. Takes no input
     µ#Ṫ  - Read an integer n from STDIN and find the nth integer, k, in
            i = 0, 1, 2, ... for which the following is True:
Ç         -   The ith Fibonacci number
 Æḍ       -   Proper divisor count
   =1     -   Equals 1?
        Ç - Yield the kth Fibonacci number

```
> 0 votes

# Answer
# CJam, 31 bytes

```
1_qi{{_@+_:T,{)T\%!}%:+2>}g}*\;

```

Try it online!

This is slow.

There is a builtin for primality checking. With that included, it runs much faster, and the size drops to 19 bytes (with the restriction that the supported maximum is 12, because CJam refuses to do a primality check on a BigInt).
> 0 votes

---
Tags: code-golf, number, primes, fibonacci
---


title: Rhombus sequence

text:
# Question
Title: Rhombus sequence
Imagine enumerating the elements of rhombi which grow `[1],[1,3,1],[1,3,5,3,1],…` (only odd numbers such that they align nicely). This would look like as follows, note that you always begin enumerating with `1`:

```
                   01
       1        02 03 04
 1   2 3 4   05 06 07 08 09          …
       5        10 11 12
                   13
(1) (1,3,1)    (1,3,5,3,1)    (1,3,5,7,5,3,1)   …

```

Now if you start summing the columns (`[1],[2],[1,3,5],[4],[5],[2,6,10],…`) you get the *rhombus sequence*. These are the first 100 elements of said sequence:

```
1,2,9,4,5,18,35,24,9,10,33,60,91,70,45,16,17,54,95,140,189,154,115,72,25,26,81,140,203,270,341,288,231,170,105,36,37,114,195,280,369,462,559,484,405,322,235,144,49,50,153,260,371,486,605,728,855,754,649,540,427,310,189,64,65,198,335,476,621,770,923,1080,1241,1110,975,836,693,546,395,240,81,82,249,420,595,774,957,1144,1335,1530,1729,1564,1395,1222,1045,864,679,490,297,100

```

## IO

You are free to choose one of these three input/output methods (you won't need to handle invalid inputs):

* Given an integer *n* output the *n*th element in that sequence (0- or 1-indexed, your choice)
* Given an integer *n* output first *n* elements of that sequence
* Print/return the sequence indefinetely

## Testcases

Please refer to the first 100 terms above, here are some larger examples (1-indexed):

```
101 -> 101
443 -> 1329
1000 -> 49000
1984 -> 164672
2017 -> 34289
2018 -> 30270
3000 -> 153000

```

# Answer
> 3 votes
## Snowman, 72 bytes

```
((}1vn2nD#`nPnCdU!*2nM1`nR:#nSNaB#`nS2nMNdE;aM|#NdE2nP+#`nSNdE`|aA#nM*))

```

This is a subroutine that takes 1-indexed input and returns the corresponding output via the permavar `+`.

Try it online!

```
((        // begin subroutine
 }        // we'll only need 3 variables - b, e, g
 1vn2nD   // b = 0.5
 #`       // retrieve input and swap, now b = input and e = 0.5
 nP       // power, resulting in b=sqrt(input)
 nC       // ceiling - this gives the index i of the rhombus we want
 dU!*     // keep a copy of i in the permavar ! for later use
 2nM1`nR  // generate the range [1, 2i)
 :        // map the following block over the range...
  #nS     // subtract i, resulting in e.g. [-3 -2 -1 0 1 2 3] for i=4
  NaB     // absolute value - [3 2 1 0 1 2 3]
  #`nS    // subtract from i, giving [1 2 3 4 3 2 1]
  2nMNdE  // double and decrement, [1 3 5 7 5 3 1]
 ;aM      // map
 |        // shove the rhombus columns into g
 #NdE2nP  // b = (i-2)^2
 +#`      // move b into e and replace it with the original input
 nSNdE    // subtract the two and decrement, giving input-(i-2)^2-1
 `|aA     // this is the index into the rhombus columns that we want
 #nM*     // multiply by the original input and return
))

```

This uses basically the same algorithm as Mr. Xcoder's answer—the only difference is that here we only generate the columns of the rhombus we need, which is the ceil(sqrt(n))th one. To illustrate why this works, here are the inputs that correspond to each rhombus:

```
rhombus #   inputs
1           1
2           2 3 4
3           5 6 7 8 9
4           10 11 12 13 14 15 16
...

```

Note that the left column corresponds exactly to the ceiling of the square root of each element in the right column. To get the 1-based index from here, we simply subtract the square of the index of the previous rhombus.

# Answer
> 2 votes
# Jelly, 10 bytes

```
Ḥ€€’ŒBFị@×

```

Try it online!

A full program / monadic link returning the **N**th term (1-indexed).

> I noticed that each sum is the index of that column in the overall list of columns (the input itself) multiplied by the index of that column in the corresponding Rhombus, so no need to actually generate the rows.

## How?

```
Ḥ€€’ŒBFị@× ~ Full program. I'll call the input N.

  €        ~ For each integer X in the range [1, N].
Ḥ€         ~ Double each integer in the range [1, X].
   ’       ~ Decrement (subtract 1).
    ŒB     ~ Bounce (element-wise). Palindromize each.
      F    ~ Flatten.
       ị@  ~ Get the element at the index N in our list.
         × ~ Multiply by N.

```

# Answer
> 2 votes
# JavaScript (ES7), ~~42~~ 41 bytes

*Saved 1 byte thanks to @ovs*

0-indexed. A closed-form expression derived from A004737.

```
n=>((k=n**.5|0)-Math.abs(n+k*~k))*2*++n+n

```

### Test cases

```
let f =

n=>((k=n**.5|0)-Math.abs(n+k*~k))*2*++n+n

console.log(f(101-1))  // 101
console.log(f(443-1))  // 1329
console.log(f(1000-1)) // 49000
console.log(f(1984-1)) // 164672
console.log(f(2017-1)) // 34289
console.log(f(2018-1)) // 30270
console.log(f(3000-1)) // 153000
```

# Answer
> 2 votes
# Befunge, ~~62~~ 60 bytes

```
&:1>:00p:*`|
00:-\*:g00:<>2-\-0v!`\g
*.@v+1<g00:<^*2g00_2*1+

```

Try it online!

**Explanation**

We start by reading the one-based element number, *n*, from stdin, and saving a duplicate.
Then we determine which rhombus we're in, by counting up an integer, *r*, until `r*r >= n`.
The column offset from the right hand side of the rhombus, *c*, is `r*r - n`.
To get that offset reflected around the centre axis, we check if `c >= r`.
And if it is, then the reflected *c* becomes `r*2 - 2 - c`.
Once we have the reflected *c*, the sum of the column is simply `(c*2 + 1) * n`.

# Answer
> 2 votes
# APL (Dyalog), 18 bytes

```
{⍵×2×⌊/|⍵-.5+×⍨⍳⍵}

```

Try it online!

# Answer
> 1 votes
# Jelly, 8 bytes

```
_.ạ²€ṂḤ×

```

Try it online!

### How it works

```
_.ạ²€ṂḤ×  Main link. Argument: n

_.        Subtract 0.5; yield (n - 0.5).
   ²€     Square each; yield [1², 2², ..., n²].
  ạ       Take the absolute differences of (n - 0.5) and each of the squares.
     Ṃ    Take the minimum.
      Ḥ   Unhalve; double the minimum.
       ×  Multiply the result by n.

```

# Answer
> 0 votes
# Husk, 13 bytes

```
*¹D▼mo≠-.¹m□ḣ

```

Try it online!

Similar to the existing Jelly and APL answers.

# Answer
> 0 votes
# Japt, 12 bytes

```
Ñ*UÇ²a½nUÃrm

```

Try it

```
Ñ*UÇ²a½nUÃrm     :Implicit input of integer U
Ñ                :Multiply by 2
 *               :Multiply by
  UÇ             :  Map the range [0,U)
    ²            :    Square
     a           :    Absolute difference with
      ½          :      0.5
       nU        :      Subtracted from U
         Ã       :  End map
          r      :  Reduce by
           m     :    Minimum

```

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


title: Smallest Prime with a Twist (A068103)

text:
# Question
Title: Smallest Prime with a Twist (A068103)
The task at hand is, given a number `n`, find the smallest prime that starts with ***AT LEAST*** `n` of the number `2` at the beginning of the number. This is a sequence I found on OEIS (A068103).

The first 17 numbers in the sequence are given below, if you want more I'll have to actually go implement the sequence, which I don't mind doing.

```
0  = 2
1  = 2
2  = 223
3  = 2221
4  = 22229
5  = 2222203
6  = 22222223                # Notice how 6 and 7 are the same!
7  = 22222223                # It must be **AT LEAST** 6, but no more than necessary.
8  = 222222227
9  = 22222222223             # Notice how 9 and 10 are the same!
10 = 22222222223             # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221

```

Just thought this would be a cool combination of string manipulation, prime detection and sequences. This is , lowest byte count will be declared the winner probably at the end of the month.

# Answer
# Brachylog, ~~12~~ 11 bytes

```
:2rj:Acb#p=

```

Try it online!

This translates into Brachylog surprisingly directly. This is a function, not a full program (although giving the interpreter `Z` as a command-line argument causes it to add the appropriate wrapper to make the function into a program; that's what I did to make the TIO link work). It's also fairly unfortunate that `j` appears to be -1-indexed and needs a correction to allow for that.

You can make a reasonable argument that the `=` isn't necessary, but I think that given the way the problem's worded, it is; without, the function's describing the set of all prime numbers that start with the given number of `2`s, and without some explicit statement that the program should *do* something with this description (in this case, generating the first value), it probably doesn't comply with the spec.

## Explanation

```
:2rjbAcb#p=
:2rj         2 repeated a number of times equal to the input plus one
    :Ac      with something appended to it
       b     minus the first element
        #p   is prime;
          =  figure out what the resulting values are and return them

```

When used as a function returning an integer, nothing ever requests values past the first, so the first is all we have to worry about.

One subtlety (pointed out in the comments): `:Acb` and `b:Ac` are mathematically equivalent (as one removes from the start and the other adds to the end, with the region in between never overlapping); I previously had `b:Ac`, which is more natural, but it breaks on input 0 (which I'm guessing is because `c` refuses to concatenate an empty list to anything; many Brachylog builtins tend to break on empty lists for some reason). `:Acb` ensures that `c` never has to see an empty list, meaning that the case of input 0 can now work too.
> 12 votes

# Answer
# Java (OpenJDK 8), ~~164~~ 110 bytes

```
a->{int i=0;for(;!(i+"").matches("2{"+a+"}.*")|new String(new char[i]).matches(".?|(..+)\\1+");i++);return i;}

```

Thanks to @FryAmTheEggman for a bunch of bytes!

Try it online!
> 15 votes

# Answer
## Pyth, 12 bytes

```
f&!x`T*Q\2P_

```

In pseudocode:

```
f                key_of_first_truthy_value( lambda T:
  !                  not (
   x`T*Q\2               repr(T).index(input()*'2')
                     )
 &                   and
          P_T        is_prime(T)
                 )

```

Loops the `lambda` starting from `T=1`, incrementing by 1 until the condition is satisfied. The string of `2`s must be a substring from the beginning of the string, i.e. the index method needs to return `0`. If the substring is not found it returns `-1` which conveniently is also truthy, so no exceptional case exists.

You can try it online here, but the server only allows up to an input of `4`.
> 5 votes

# Answer
## Perl, 50 bytes

49 bytes of code + `-p` flag.

```
++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{

```

Supply the input without final newline. For instance:

```
echo -n 4 | perl -pE '++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{'

```

This take a while to run a numbers greater than 4 as it test every number (there are 2 test: the first one `/^2{$_}/` checks if there is enough 2 at the beginning, and the second one `(1x$\)!~/^1?$|^(11+)\1+$/` tests for primality (with very poor performances)).
> 4 votes

# Answer
## Haskell, 73 bytes

```
f n=[x|x<-[2..],all((>0).mod x)[3..x-1],take n(show x)==([1..n]>>"2")]!!0

```

Usage example: `f 3` -\> `2221`.

Brute force. `[1..n]>>"2"` creates a list of `n` `2`s which is compared to the first `n` chars in the string representation of the current prime.
> 3 votes

# Answer
# Mathematica, 103 bytes

```
ReplaceRepeated[0,i_/;!IntegerDigits@i~MatchQ~{2~Repeated~{#},___}||!PrimeQ@i:>i+1,MaxIterations->∞]&

```

Unnamed function taking a nonnegative integer argument `#` and returning an integer. It literally tests all positive integers in turn until it finds one that both starts with `#` 2s and is prime. Horribly slow for inputs above 5.

previous result: **Mathematica, 155 bytes**

Mathematica would be better for golfing if it weren't so strongly typed; we have to explicitly switch back and forth between integer/list/string types.

```
(d=FromDigits)[2&~Array~#~Join~{1}//.{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}//.{a__,b_,10,c___}->{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b})]/. 23->2&

```

This algorithm operates on *lists of digits*, strangely, starting with `{2,...,2,1}`. As long as those aren't the digits of a prime number it adds one to the last digit, using the rule `{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}` ... and then manually implements carrying-the-one-to-the-next-digit as long as any of the digits equal 10, using the rule `{a__,b_,10,c___}->{a,b+1,0,c}` ... and then, if we've gone so far that the last of the leading `2`s has turned into a `3`, starts over with another digit on the end, using the rule `{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}`. The `/. 23->2` at the end just fixes the special case where the input is `1`: most primes can't end in `2`, but `2` can. (A few errors are spat out on the inputs `0` and `1`, but the function finds its way to the right answer.)

This algorithm is quite fast: for example, on my laptop it takes less than 3 seconds to compute that the first prime starting with 1,000 `2`s is `22...220521`.
> 3 votes

# Answer
# Pyth, 17 bytes

```
f&q\2{<`T|Q1}TPTh

```

Can't seem to solve over `n = 4` online, but it's correct in theory.

### Explanation

```
               Th    Starting from (input)+1,
f                    find the first T so that
      <              the first
          Q          (input) characters
         | 1         or 1 character, if (input) == 0
       `T            of T's string representation
     {               with duplicates removed
  q\2                equal "2",
 &                   and
            }T       T is found in
              PT     the list of T's prime factors.

```
> 2 votes

# Answer
# Perl 6, 53 bytes

```
{($/=2 x$^n-1)~first {+($/~$_) .is-prime&&/^2/},0..*}

```

Try it

## Expanded:

```
{
  ( $/ = 2 x $^n-1 )       # add n-1 '2's to the front (cache in ｢$/｣)
  ~
  first {
    +( $/ ~ $_ ) .is-prime # find the first that when combined with ｢$/｣ is prime
    &&
    /^2/                   # that starts with a 2 (the rest are in ｢$/｣)
  },
  0..*
}

```
> 2 votes

# Answer
# Jelly, 14 bytes

```
D=2×\S:³aÆPµ1#

```

*Very* inefficient. Try it online!
> 2 votes

# Answer
## Sage, ~~69~~ 68 bytes

```
lambda n:(x for x in Primes()if '2'*len(`x`)=>'2'*n==`x`[:n]).next()

```

Uses a generator to find the first (hence smallest) of infinitely many terms.
> 2 votes

# Answer
## Pyke, 14 bytes

```
.fj`Q\2*.^j_P&

```

Try it here!

```
.fj            - first number (asj)
   `    .^     -   str(i).startswith(V)
    Q\2*       -    input*"2"
             & -  ^ & V
          j_P  -   is_prime(j)

```

### 12 bytes after bugfix and a new feature

```
~p#`Q\2*.^)h

```

Try it here!

```
~p           - all the primes
  #       )h - get the first where...
   `    .^   - str(i).startswith(V)
    Q\2*     -  input*"2"

```
> 2 votes

# Answer
# Japt, 20 bytes

```
L²o@'2pU +Xs s1)nÃæj

```

Test it online! It finishes within two seconds on my machine for all inputs up to 14, and after that it naturally loses precision (JavaScript only has integer precision up to 253).

Many thanks to @obarakon for working on this :-)

### Explanation

```
                       // Implicit: U = input integer, L = 100
L²o                    // Generate the range [0...100²).
   @             Ã     // Map each item X through the following function:
    '2pU               //   Take a string of U "2"s.
         +Xs s1)n      //   Append all but the first digit of X, and cast to a number.
                       // If U = 3, we now have the list [222, 222, ..., 2220, 2221, ..., 222999].
                  æ    // Take the first item that returns a truthy value when:
                   j   //   it is checked for primality.
                       // This returns the first prime in the forementioned list.
                       // Implicit: output result of last expression

```

---

In the latest version of Japt, this can be 12 bytes:

```
_n j}b!+'2pU   // Implicit: U = input integer
_   }b         // Return the first non-negative bijective base-10 integer that returns
               // a truthy value when run through this function, but first,
      !+       //   prepend to each integer
        '2pU   //   a string of U '2's.
               // Now back to the filter function:
 n j           //   Cast to a number and check for primality.
               // Implicit: output result of last expression

```

Test it online! It finishes within half a second on my machine for all inputs up to 14.
> 2 votes

# Answer
# PHP, 76 bytes

```
for($h=str_pad(2,$i=$argv[1],2);$i>1;)for($i=$p=$h.++$n;$p%--$i;);echo$p?:2;

```

takes input from command line argument. Run with `-r`.

**breakdown**

```
for($h=str_pad(2,$i=$argv[1],2) # init $h to required head
    ;$i>1;                      # start loop if $p>2; continue while $p is not prime
)
    for($i=$p=$h.++$n               # 1. $p = next number starting with $h
                                    #    (first iteration: $p is even and >2 => no prime)
    ;$p%--$i;);                     # 2. loop until $i<$p and $p%$i==0 ($i=1 for primes)
echo$p?:2;                      # print result; `2` if $p is unset (= loop not started)

```
> 2 votes

# Answer
# Bash (+coreutils), 53 bytes

Works up to *2^63-1 (9223372036854775807)*, takes considerable time to finish for N \> 8.

**Golfed**

```
seq $[2**63-1]|factor|grep -Pom1 "^2{$1}.*(?=: \S*$)"

```

**Test**

```
>seq 0 7|xargs -L1 ./twist

2
2
223
2221
22229
2222203
22222223
22222223

```
> 1 votes

# Answer
## Python 3, 406 bytes

```
w=2,3,5,7,11,13,17,19,23,29,31,37,41
def p(n):
 for q in w:
  if n%q<1:return n==q
  if q*q>n:return 1
 m=n-1;s,d=-1,m
 while d%2==0:s,d=s+1,d//2
 for a in w:
  x=pow(a,d,n)
  if x in(1,m):continue
  for _ in range(s):
   x=x*x%n
   if x==1:return 0
   if x==m:break
  else:return 0
 return 1
def f(i):
 if i<2:return 2
 k=1
 while k:
  k*=10;l=int('2'*i)*k
  for n in range(l+1,l+k,2):
   if p(n):return n

```

### test code

```
for i in range(31):
    print('{:2} = {}'.format(i, f(i)))

```

### test output

```
 0 = 2
 1 = 2
 2 = 223
 3 = 2221
 4 = 22229
 5 = 2222203
 6 = 22222223
 7 = 22222223
 8 = 222222227
 9 = 22222222223
10 = 22222222223
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
17 = 222222222222222221
18 = 22222222222222222253
19 = 222222222222222222277
20 = 2222222222222222222239
21 = 22222222222222222222201
22 = 222222222222222222222283
23 = 2222222222222222222222237
24 = 22222222222222222222222219
25 = 222222222222222222222222239
26 = 2222222222222222222222222209
27 = 2222222222222222222222222227
28 = 222222222222222222222222222269
29 = 2222222222222222222222222222201
30 = 222222222222222222222222222222053

```

---

I decided to go for speed over a fairly large range, rather than byte size. :) I use a deterministic Miller-Rabin primality test which is guaranteed up to 3317044064679887385961981 with this set of witnesses. Larger primes will always successfully pass the test, but some composites may also pass, although the probability is *extremely* low. However, I also tested the output numbers for i \> 22 using pyecm an Elliptic Curve factorization program, and they appear to be prime.
> 1 votes

# Answer
## Python 3, 132 bytes

```
def f(x):
 k=10;p=2*(k**x//9)
 while x>1:
  for n in range(p*k,p*k+k):
   if all(n%q for q in range(2,n)):return n
  k*=10
 return 2

```

Any hope of performance has been sacrificed for a smaller byte count.
> 1 votes

# Answer
# Husk, 10 bytes

```
ḟo`€R⁰2dİp

```

Try it online!

A bit slow due to uusing the infinite list of primes.
> 0 votes

# Answer
**Java, 163 bytes**

```
BigInteger f(int a){for(int x=1;x>0;x+=2){BigInteger b=new BigInteger(new String(new char[a]).replace("\0","2")+x);if(b.isProbablePrime(99))return b;}return null;}

```

test code

```
    public static void main(String[] args) {
    for(int i = 2; i < 65; i++)
        System.out.println(i + " " + new Test20170105().f(i));
    }

```

output:

```
2 223
3 2221
4 22229
5 2222219
6 22222223
7 22222223
8 222222227
9 22222222223
10 22222222223
11 2222222222243
12 22222222222229
13 22222222222229
14 222222222222227
15 222222222222222143
16 222222222222222221
17 222222222222222221
18 22222222222222222253
19 222222222222222222277
20 2222222222222222222239
21 22222222222222222222261
22 222222222222222222222283
23 2222222222222222222222237
24 22222222222222222222222219
25 222222222222222222222222239
26 2222222222222222222222222213
27 2222222222222222222222222227
28 222222222222222222222222222269
29 22222222222222222222222222222133
30 222222222222222222222222222222113
31 222222222222222222222222222222257
32 2222222222222222222222222222222243
33 22222222222222222222222222222222261
34 222222222222222222222222222222222223
35 222222222222222222222222222222222223
36 22222222222222222222222222222222222273
37 222222222222222222222222222222222222241
38 2222222222222222222222222222222222222287
39 22222222222222222222222222222222222222271
40 2222222222222222222222222222222222222222357
41 22222222222222222222222222222222222222222339
42 222222222222222222222222222222222222222222109
43 222222222222222222222222222222222222222222281
44 2222222222222222222222222222222222222222222297
45 22222222222222222222222222222222222222222222273
46 222222222222222222222222222222222222222222222253
47 2222222222222222222222222222222222222222222222219
48 22222222222222222222222222222222222222222222222219
49 2222222222222222222222222222222222222222222222222113
50 2222222222222222222222222222222222222222222222222279
51 22222222222222222222222222222222222222222222222222289
52 2222222222222222222222222222222222222222222222222222449
53 22222222222222222222222222222222222222222222222222222169
54 222222222222222222222222222222222222222222222222222222251
55 222222222222222222222222222222222222222222222222222222251
56 2222222222222222222222222222222222222222222222222222222213
57 222222222222222222222222222222222222222222222222222222222449
58 2222222222222222222222222222222222222222222222222222222222137
59 22222222222222222222222222222222222222222222222222222222222373
60 222222222222222222222222222222222222222222222222222222222222563
61 2222222222222222222222222222222222222222222222222222222222222129
62 2222222222222222222222222222222222222222222222222222222222222227
63 2222222222222222222222222222222222222222222222222222222222222227
64 2222222222222222222222222222222222222222222222222222222222222222203

```

582.5858 milliseconds

Explanation: loops over integers and adds them as strings to the root string, which is the given "2's" string, and verifies if it's prime or not.
> -1 votes

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


# Question
Title: Write a function that reduces compositions of linear operators
You are given two functions \\$g(x)\\$ and \\$h(x)\\$, each of which takes an integer \\$x\\$ and returns the number \\$ax + b\\$ (where \\$a\\$ and \\$b\\$ are integers defined in the function).

Your task is to write a function \\$f(g, h)\\$ that takes these two functions, and returns a function \\$k(x) = g(h(x))\\$, but where the procedure of \\$k(x)\\$ is also simply of the form \\$ax + b\\$.

For example, given \\$g(x) = 2x + 3\\$ and \\$h(x) = 3x + 4\\$, you would need to return \\$k(x) = 6x + 11\\$, and not \\$k(x) = 2(3x + 4) + 3\\$.

# Answer
> 3 votes
### GolfScript, 41 40 23 19 characters

```
{2,0+%/-{@*+}++}:k;

```

Thanks to Peter Taylor for pointing out this solution. Accepts two function bodies as arguments.

The following examples show how to use function `k`:

```
# As function
{2*3+} {3*4+} k         # => {11 6 @*+}

# Apply to value
5 {2*3+} {3*4+} k ~     # => 41

```

If one wants to retain the original output format, the following 22 character solution is possible:

```
{2,0+%/-{*}+\+{+}+}:k;

{2*3+} {3*4+} k         # => {6 * 11 +}

```

Explanation of the code:

```
{                       # on stack are functions g h
  2,                    # build array [0 1] -> g h [0 1]
  0+                    # append 0 -> g h [0 1 0]
  %                     # apply function h to each element -> g [h(0) h(1) h(0)]
  /                     # apply function g to each element
                        # and break up the array -> g(h(0)) g(h(1)) g(h(0))
  -                     # subtract last two -> g(h(0)) g(h(1))-g(h(0))
  {@*+}++               # append function body to these values
}:k;                    # save function to variable k

```

# Answer
> 2 votes
# Mathematica 15

**Define g, h as pure functions**

`g` and `h` are defined as pure functions (awaiting a value or independent variable to be assigned)

```
g = 2 # + 3 &;
h = 3 # + 4 &;
g[x]
h[x]

```

> 3 + 2 x
> 4 + 3 x

---

**Method #1: Compose `g` of `h` directly** (15 chars)

```
g@h@x//Simplify

```

> 11 + 6 x

Or, alternatively: (17 chars)

```
g[h[x]]//Simplify

```

---

**Method #2: Define `f`** (25 chars= 13 + 10 chars for Simplify)

```
f=Composition

```

```
f[g, h][x]
f[g, h][x] // Simplify
Composition[g, h][x]//Simplify
f[g, h][1]
Table[f[g, h][x], {x, 1, 13}]

```

> 3 + 2 (4 + 3 x)
> 11 + 6 x
> 11 + 6 x
> 17
> {17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89}

# Answer
> 2 votes
### Haskell, 31

```
(f%g)x=f(g 0)+x*(f(g 1)-f(g 0))

```

Version in which the function body contains only variables (equivalent at run time, but closer to the question's form), 38 characters:

```
(f%g)x=a*x+b where h=f.g;b=h 0;a=h 1-b

```

Note that in both cases, since Haskell uses curried functions, there is no explicit construction of the composed function as it is implicit in `%` being defined with three arguments: function f, function g, value x.

Example use:

```
> ((\x -> 2*x + 3)%(\x -> 3*x + 4)) 0
11
> ((\x -> 2*x + 3)%(\x -> 3*x + 4)) 4
35

```

Ungolfed second form:

```
(f % g) x = a * x + b        -- equivalent: (f % g) = \x -> a * x + b
  where
    h = f . g                -- use built in function composition to bootstrap
    b = h 0                  -- constant term of composed function
    a = h 1 - h 0            -- linear term of composed function

```

# Answer
> 1 votes
## vba, 89

```
Function f(g,h,x)
f=Evaluate(Replace(g,"x","*("&Replace(h,"x","*"&x)&")"))
End Function

```

usage/result

> ?f("2x+3","3x+4",1)
> 17

# Answer
> 1 votes
## Lua, 87

```
function f(g, h)local a,b=g(h(1))-g(h(0)),g(h(0))return function(x)return a*x+b end end

```

# Answer
> 1 votes
# Ruby \>=1.9, 55

```
f=->g,h{a=(g[1]-g[0])*(h[1]-h[0]);b=g[h[0]];->x{a*x+b}}

```

Less golfed:

```
def c(f,g)
  f_a=f[1]-f[0]
  g_a=g[1]-g[0]
  a=f_a*g_a
  b=f[g[0]]
  ->x{a*x+b}
end

```

# Answer
> 1 votes
## SML (60 chars)

```
fun f g h=let val c=g(h 0)val m=g(h 1)-c in fn x=>m*x+c end;

```

Ungolfed:

```
fun f g h =
    let val c = g (h 0)
        val m = g (h 1) - c
     in fn x => m*x + c
    end;

```

# Answer
> 1 votes
# Jelly, ~~22~~ 13 bytes

```
vØ.v@µI,Ḣż⁾×+

```

Try it online!

I think I understand what the question is asking for, but it really isn't clear exactly *how* the program is supposed to return \\$a\\$ and \\$b\\$, and it seems as though (given the tag) that this is an unobservable requirement)

~~11 bytes sacrificed to clumsy I/O formats.~~

-9 bytes thanks to Howard's method

This takes \\$g\\$ and \\$h\\$ in Jelly's most natural form for non-black-box functions, as a string representing a Jelly link. As \\$g(x)=ax+b\\$ (and similar for \\$h\\$), this is equivalent to `a×b+`. We also return \\$k\\$ in the form `a×b+`. If this can instead take input and output as two lists `[a, b]` representing \\$g\\$ and \\$h\\$, we can reduce this to 8 bytes.

## How it works

```
vØ.v@µI,Ḣż⁾×+ - Main link. Takes h ("c×d+") on the left and g ("a×b+") on the right
 Ø.           - [0, 1]
v             - Run h over each; [h(0), h(1)]
   v@         - Run g over each; [g(h(0)), g(h(1))]
     µ        - New link. Call this pair l and use it as the argument
      I       - Differences; g(h(0)) - g(h(1))
        Ḣ     - Head; g(h(0))
       ,      - Pair; [g(h(0)) - g(h(1)), g(h(0))]
          ⁾×+ - Yield "×+"
         ż    - Zip together; [g(h(0)) - g(h(1)), "×", g(h(0)), "+"]
                Implicitly smash together and print

```

# Answer
> 0 votes
# PHP 72

Apparently I completely missed the point of this code-golf. I'm STILL not sure if I understand it correctly. Is no output required? Can I assume the methods of g and h? Here's a new version based off the old one:

```
<?=$f=function($g,$h,$x){return$k=($g[0]*$h[0]*$x)+($g[0]*$h[1])+$g[1];}

```

If this is still wrong, I give up.

---

# PHP 176

The requirements are kind of confusing, but here's what I think you meant:

```
<?=f($argv);function f($a){$x=$a[3];$g=explode("x",$a[1]);$h=explode("x",$a[2]);return$k=($g[0]*$h[0])."*$x+".(($g[0]*$h[1])+$g[1])."=".(($g[0]*$h[0]*$x)+($g[0]*$h[1])+$g[1]);}

```

Usage: `php f.php 2x+3 3x+4 5`

Output: `6*5+11=41`

Another Example

Usage: `php f.php 4x-7 3x+4 2`

Output: `12*2+9=33`

# Method

As you described, we can't simply output the answer with `g(h(x))`, we had to create function `f(g,h)` which determines what both the functions would be **together,** and return that as a new function: `k(x)`.

Is this what OP meant?

**Ungolfed**

```
<?php

function f($a) {
    $x=$a[3];
    $g=explode("x",$a[1]);
    $h=explode("x",$a[2]);
    $k  = $g[0]*$h[0];
    $k .= "*";
    $k .= $x;
    $k .= "+";
    $k .= ($g[0]*$h[1])+$g[1];
    $k .= " = ";
    $k .= ($g[0]*$h[0]*$x) + ($g[0]*$h[1])+$g[1];
    return $k;
}

echo f($argv);

```

# Answer
> 0 votes
**Erlang 54:**

```
1> F = fun(G,H)->B=G(H(0)),A=G(H(1))-B,fun(X)->A*X+B end end.
2> (F(fun(X) -> 2*X+3 end, fun(X) -> 3*X + 4 end))(0).
11
3> (F(fun(X) -> 2*X+3 end, fun(X) -> 3*X + 4 end))(1) - v(2).
6

```

# Answer
> 0 votes
Common Lisp (108)

```
(defun f(g h)(let*((d(g 0))(c(-(g 1)d))(z(h 0))(e(-(h 1)z))(a(* c e))(b(+(* c z)d)))(lambda(x)(+(* a x)b))))

```

It could be shorter if I assumed expressions would have constants folded...but I didn't make that assumption to make sure I met the spec. Also, I have implemented Clojure's literal anonymous function syntax as a read macro. I decided against using that as well.

# Answer
> 0 votes
## Postscript, 120

```
/f{1 index 0 get dup
2 index 0 get mul exch
3 2 roll 2 get mul
3 2 roll 2 get add[3 1 roll/mul cvx exch/add cvx]cvx}def

```

Ungolfed and commented with testing.

```
/g{2 mul 3 add}def
/h{3 mul 4 add}def

/f{
    1 index 0 get % g h g[0]
    dup 2 index 0 get mul % g h g[0] g[0]*h[0]
    exch 3 2 roll 2 get mul % g g[0]*h[0] g[0]*h[2]
    3 2 roll 2 get add % g[0]*h[0] g[0]*h[2]+g[2]
    [ 3 1 roll /mul cvx exch /add cvx ] cvx
}def

//g //h f ==

```

Output:

```
GPL Ghostscript 9.10 (2013-08-30)
Copyright (C) 2013 Artifex Software, Inc.  All rights reserved.
This software comes with NO WARRANTY: see the file PUBLIC for details.
{6 mul 11 add}
GS>

```

---
Tags: code-golf, functional-programming
---