title: Find the Smoothest Number

text:
# Question
Title: Find the Smoothest Number
Your challenge is to find the smoothest number over a given range. In other words, find the number whose greatest prime factor is the smallest.

A smooth number is one whose largest prime factor is small. Numbers of this type are useful for the fast Fourier transform algorithm, cryptanalysis, and other applications.

For instance, over the range `5, 6, 7, 8, 9, 10`, 8 is the smoothest number, because 8's greatest prime factor is 2, whereas all of the other numbers have a prime factor of 3 or greater.

**Input:** The input will be two positive integers, which define a range. The minimum allowable integer in the range is 2. You may choose whether the range is inclusive, exclusive, semi-exclusive, etc, as long as an arbitrary range can be specified within the bounds of your language. You may take the numbers via function input, stdin, command line argument, or any equivalent method for your language. No encoding extra information in the input.

**Output:** Return, print or equivalent one or more integers in the input range which are maximally smooth (minimal greatest factor). Returning multiple results is optional, but if you choose to do so the results must be clearly delimited. Native output format is fine for multiple results.

Please state in your answer how you are taking input and giving output.

**Scoring:** Code golf. Count by characters if written in ASCII, or 8\*bytes/7 if not in ASCII.

**Test cases:**

Note: These are Python-style ranges, including the low end but not the high end. Change as appropriate to your program. Only one result is necessary.

```
smooth_range(5,11)
8
smooth_range(9,16)
9, 12
smooth_range(9,17)
16
smooth_range(157, 249)
162, 192, 216, 243
smooth_range(2001, 2014)
2002

```

# Answer
# CJam - 13

```
q~,>{mfW=}$0=

```

Try it at http://cjam.aditsu.net/

Example input: `2001 2014`
Example output: `2002`

**Explanation:**

`q~` reads and evaluates the input, pushing the 2 numbers on the stack (say min and max)
`,` makes an array \[0 1 ... max-1\]
`>` slices the array starting at min, resulting in \[min ... max-1\]
`{…}$` sorts the array using the block to calculate the sorting key
`mf` gets an array with all the prime factors of a number, in order
`W=` gets the last element of the array (W=-1), thus obtaining the largest prime factor to be used as a sorting key
`0=` gets the first element of the (sorted) array
> 100 votes

# Answer
## Regex (~~.NET~~ PCRE flavour), ~~183~~ 129 bytes

Don't try this at home!

This is not really a contender for the win. But Eric Tressler suggested solving this problem with nothing but a regex, and I couldn't resist giving it a go. This ~~might be~~ is possible in PCRE as well (and even shorter, see below), but I chose .NET because my solution needs arbitrary-length lookbehinds. Here we go:

```
(?<=^(1+),.*)(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((11+)(?=.*(?=\7$)(?!(11+?)\8+$))(?=\7+$)|(?!(11+)\9+$)1+)).*(?=\2$)(?=\6)))1+

```

The input is encoded as an inclusive comma-separated range, where both numbers are given in unary notation using `1`s. The match will be the trailing `S` 1s where `S` is the smoothest number in the range. Ties are broken in favour of the smallest number.

So the second example from the question would be the following string (match underlined)

```
111111111,1111111111111111
                 =========

```

It is based on the (by now rather well-known) prime-checking regex, variations of which are embedded in there a whopping 6 times.

Here is a version using free-spacing and comments for those who want to know what's going on.

```
# Note that the beginning of the match we're looking for is somewhere
# in the second part of the input.
(?<=^(1+),.*)          # Pick up the minimum range MIN in group 1
(?=\1)                 # Make sure there are at least MIN 1s ahead

                       # Now there will be N 1s ahead of the cursor
                       # where MIN <= N <= MAX.

(?=(                   # Find the largest prime factor of this number
                       # store it in group 2.
  (11+)                # Capture a potential prime factor P in group 3
  (?=                  # Check that it's prime
    .*(?=\3$)          # Move to a position where there are exactly
                       # P 1s ahead
    (?!(11+?)\4+$)     # Check that the remaining 1s are not composite
  )
  (?=\3+$)             # Now check that P is a divisor of N.
|                      # This does not work for prime N, so we need a
                       # separate check
  (?!(11+)\5+$)        # Make sure that N is prime.
  1+                   # Match N
))

(?!                    # Now we need to make sure that here is not
                       # another (smaller) number M with a smaller
                       # largest prime factor

  .+                   # Backtrack through all remaining positions
  (?=\1)               # Make sure there are still MIN 1s ahead

  (?:
    (?!\2)             # If M is itself less than P we fail
                       # unconditionally.
  |                    # Else we compare the largest prime factors.
    (?=(               # This is the same as above, but it puts the
                       # prime factor Q in group 6.
      (11+)
      (?=
        .*(?=\7$)
        (?!(11+?)\8+$)
      )
      (?=\7+$)
    |
      (?!(11+)\9+$)
      1+
    ))
    .*(?=\2$)          # Move to a position where there are exactly
                       # P 1s ahead
    (?=\6)             # Try to still match Q (which means that Q is
                       # less than P)
  )
)
1+                     # Grab all digits for the match

```

You can test it online over here. Don't try too large inputs though, I make no guarantees about the performance of this monster.

**Edit:**

I ended up porting this to PCRE (which only requires two steps), and shortening the regex by almost a third. Here is the new version:

```
^(1+),.*?\K(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((?2))).*(?=\2$)(?=\6)))1+

```

This is essentially the same, with two changes:

* PCRE does not support arbitrary-length lookbehind (which I used to get the `MIN` into group `1`). However, `PCRE` does support `\K` which resets the beginning of the match to the current cursor position. Hence `(?<=^(1+),.*)` becomes `^(1+),.*?\K`, which already saves two bytes.
* The real savings come from PCRE's recursion feature. I'm not actually using recursion, but you can use `(?n)` to match group `n` again, similar to a subroutine call. Since the original regex contained the code for finding a number's largest prime factor twice, I was able to replace the whole bulk of the second one with a simple `(?2)`.
> 75 votes

# Answer
# Regex (Perl / PCRE), ~~66~~ 65 (64) bytes

Inspired by seeing that both Martin Ender and jaytea, two regex geniuses, wrote regex solutions to this code golf, I wrote my own from scratch. The famous prime-checking regex does not appear anywhere in my solution.

Do not read this if you don't want some unary regex magic spoiled for you. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex:

1. Match prime numbers (if you aren't already familiar with doing this in regex)
2. Match powers of 2 (if you haven't already done so). Or just work your way through Regex Golf, which includes Prime and Powers. Make sure to do both the Classic and Teukon problem sets.
3. > Find the shortest way to match powers of N where N is some constant (i.e. specified in the regex, not the input) which can be composite (but is not required to be). For example, match powers of 6.
4. > Find a way of matching Nth powers, where N is some constant \>=2. For example, match perfect squares. (For a warmup, match prime powers.)
5. > Match correct multiplication statements. Match triangular numbers.
6. > Match Fibonacci numbers (if you're as crazy as I am), or if you want to stick to something shorter, match correct statements of exponentiation (for a warmup, return as a match the logarithm in base 2 of a power of 2 – bonus, do the same for any number, rounding it however you like), or factorial numbers (for a warmup, match primorial numbers).
7. > Match abundant numbers (if you're as crazy as I am)
8. > Calculate an irrational number to requested precision (e.g. divide the input by the square root of 2, returning the rounded result as a match)

(The regex engine I wrote may be of help, as it is very fast at unary math regexes and includes a unary numerical mode which can test ranges of natural numbers (but also has a strings mode which can evaluate non-unary regexes, or unary with delimiters). By default it is ECMAScript compatible, but has optional extensions (which can selectively add subsets of PCRE, or even molecular lookahead, something that no other regex engine has).)

Otherwise, read on, and also read this GitHub Gist (warning, many spoilers) which chronicles the journey of pushing ECMAScript regex to tackle natural number functions of increasing difficulty (starting with teukon's set of puzzles, not all of them mathematical, which sparked this journey).

As with the other regex solutions to this problem, the input is given as two numbers in bijective unary, separated by a comma, representing an inclusive range. Only one number is returned. The regex could be modified to return all of the numbers that share the same smallest largest prime factor, as separate matches, but that would require variable-length lookbehind and either putting `\K` in a lookahead or returning the result as a capture instead of a match.

The technique used here of repeated implicit division by smallest prime factor is identical to that used in the Match strings whose length is a fourth power answer I posted a while back.

With no further ado:

```
((.+).*),(?!.*(?=\1)((?=(..+)(\4+$))\5)*(?!\2)).*(?=\1)\K(?3)*\2$

```

Try it online! \- Perl
Try it online! \- PCRE
Try it on regex101

And the free-spacing version, with comments:

```
                        # No ^ anchor needed, because this algorithm always returns a
                        # match for valid input (in which the first number is less than
                        # or equal to the second number), and even in /g mode only one
                        # match can be returned. You can add an anchor to make it reject
                        # invalid ranges.

((.+).*),               # \1 = low end of range; \2 = conjectured number that is the
                        # smallest number in the set of the largest prime factor of each
                        # number in the range; note, it is only in subsequent tests that
                        # this is implicitly confined to being prime.
                        # We shall do the rest of our work inside the "high end of range"
                        # number.

(?!                     # Assert that there is no number in the range whose largest prime
                        # factor is smaller than \2.
  .*(?=\1)              # Cycle tail through all numbers in the range, starting with \1.

  # Subroutine call (?3) - defines one loop iteration, and needs to be called as (?3)*
  # Finds the largest prime factor of tail, and leaves it in tail. It will both be
  # evaluated here as-is, and later as a subroutine call. Here, it's followed by an
  # assertion that tail is less than something; if this fails to match, the regex
  # engine will try to backtrack, but that will never result in a match because
  # backtracking will only make tail larger.
  (                     # Repeatedly divide tail by its smallest prime factor, leaving
                        # only the largest prime factor at the end.

    (?=(..+)(\4+$))     # \5 = tool to make tail = \4 = largest nontrivial factor of
                        # current tail, which is implicitly the result of dividing it
                        # by its smallest prime factor.
    \5                  # tail = \4
  )*
  (?!\2)                # matches iff tail < \ 2
)

# At this point, \2 is guaranteed to be less than or equal to the smallest number in the
# set containing the largest prime factor of each of the numbers in the inputted range.
# The first time the regex engine reaches this point, \2 will be equal to the smallest
# number in that set, but if it backtracks, \2 will become smaller.

# now, pick a number in the range whose largest prime factor is \2
.*(?=\1)                # Cycle tail through all numbers in the range, starting with \1.
\K                      # Set us up to return tail as the match.
(?3)*                   # tail = largest prime factor of tail
\2$                     # Match iff tail == \2, then return the number whose largest
                        # prime factor is \2 as the match. If this fails to match, the
                        # regex engine will try to backtrack, but that will never result
                        # in a match, because backtracking makes tail a composite number
                        # that is larger than the largest prime factor of the currently
                        # marked return value, which makes it larger than any value \2
                        # can have.

```

Note that `((.+).*)` can be changed to `((.+)+)`, dropping the size by 1 byte (from 65 to **64 bytes**) with no loss of correct functionality – but the regex exponentially explodes in slowness:

```
((.+)+),(?!.*(?=\1)((?=(..+)(\4+$))\5)*(?!\2)).*(?=\1)\K(?3)*\2$

```

Try it online! \- Perl
Try it online! \- PCRE

# Regex (ECMAScript), 80 (79) bytes

The algorithm can be easily ported to ECMAScript by replacing the subroutine call with a copy of the subroutine, and returning the match as capture group `\6` instead of using `\K`. The result is **80 bytes** in length:

```
((x+)x*),(?!.*(?=\1)((?=(xx+)(\4+$))\5)*(?!\2)).*(?=\1)(((?=(xx+)(\8+$))\9)*\2$)

```

Try it online! \- **80 byte** version
Try it online! \- **79 byte** exponential-slowdown version (amazingly, this can handle all the test cases in 49 seconds)
> 20 votes

# Answer
# Python 2, 95

```
i=input()
for a in range(*i):
 s=a;p=2
 while~-a:b=a%p<1;p+=1-b;a/=p**b
 if p<i:i=p;j=s
print j

```

Finds the smoothness of the the numbers by trial division until the number is 1. `i` stores the smallest smoothness so far, `j` stores the number that gave that smoothness.

Thanks to @xnor for the golfs.
> 11 votes

# Answer
## Mathematica, ~~61~~ ~~45~~ 39 characters

```
Range@##~MinimalBy~Last@*FactorInteger&

```

Very straightforward implementation of the spec as an unnamed function.

* Get the range (inclusive).
* Factor all integers.
* Find the minimum, sorted by largest prime factor.
> 10 votes

# Answer
## J, ~~22 20~~ 19 chars

```
({.@/:{:@q:)@(}.i.)

```

E.g.

```
   2001 ({.@/: {:@q:)@(}. i.) 2014
2002

```

(Functions taking two arguments are infix in J.)
> 10 votes

# Answer
# Haskell, ~~96~~ ~~94~~ ~~93~~ ~~86~~ 80 characters

```
x%y|x<2=y|mod x y<1=div x y%y|0<1=x%(y+1)
a#b=snd$minimum$map(\x->(x%2,x))[a..b]

```

usage via GHCi (a Haskell shell):

```
>5 # 9
8
>9 # 15
9

```

**EDIT:** now a much simpler algorithm.

this solution includes both numbers in the range (so `8 # 9` and `7 # 8` are both 8)

explanation:

the (%) function takes two parameters, x and y. when y is 2, the function returns the smoothness of x.

the algorithm from here is simple - get the combined list of all smoothnesses of numbers in the input with each smoothness storing a reference to it's original number, sort then to get the smallest, and return it's referenced number.

here is an ungolfed javascript version with the same algorithm:

```
function smoothness(n,p)
{
    p = p || 2
    if (x == 1)
        return p
    if (x % p == 0)
        return smoothness(x/p, p)
    else
        return smoothness(x,p+1);
}
function smoothnessRange(a, b)
{
    var minSmoothness = smoothness(a);
    var min=a;
    for(var i=a+1;i <= b;i++)
        if(minSmoothness > smoothness(i))
        {
            minSmoothness = smoothness(i)
            min = i
        }
    return min;
}

```
> 9 votes

# Answer
# Bash+coreutils, 56 bytes

```
seq $@|factor|sed 's/:.* / /'|sort -nk2|sed '1s/ .*//;q'

```

Input is from from exactly two command-line arguments (Thanks @nyuszika7h !!!). Output is a singular result printed to STDOUT.

* `seq` provides the range of numbers, one per line, from the command-line arguments.
* `factor` reads those numbers and outputs each number followed by a colon and the sorted list of prime factors of that number. So the largest prime factor is at the end of each line.
* The first `sed` removes the colon and all but the last/largest prime factor, so leaves a list of each number (column 1) and its largest prime factor (column 2).
* `sort` numerically in increasing order by the column 2.
* The final `sed` matches line 1 (number whose largest prime factor is the smallest in the list), removes everything including and after the first space, then quits. `sed` automatically prints the result of this substitution before quitting.

### Output:

```
$ ./smooth.sh 9 15
12
$ ./smooth.sh 9 16
16
$ ./smooth.sh 157 249
162
$ ./smooth.sh 2001 2014
2002
$

```

Note ranges in this context are *inclusive* of both endpoints.
> 8 votes

# Answer
# Lua - 166 chars

*I ~~don't~~didn't have (yet!) enough reputation to comment on AndoDaan's solution, but here are some improvements on his code*

```
a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d<1 do f[#f+1]=d n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

```

Changes :

* The `n%d==0` by `n%d<1` which is equivalent in this case
* Removed a space
* Replaced `table.insert(f,d)` by `f[#f+1]=d` (`#f` is the number of elements of f)
> 8 votes

# Answer
# Python 2, 67

```
f=lambda R,F=1,i=2:[n for n in range(*R)if F**n%n<1]or f(R,F*i,i+1)

```

Thinking about another golf gave me an idea for a new algorithm to check smoothness, hence the late answer.

The prime factorization of the factorial `i!` includes exactly the primes at most `i`. So, if `n` is a product of distinct primes, its smoothness (largest prime factor) is the smallest `i` for which `n` is a divisor of `i!`. To account for repeated prime factors in `n`, we can instead use a sufficiently high power of `i!`. In particular, `(i!)**n` suffices.

The code tries increasing factorials `F=i!`, updated recursively. We filter for the divisors of `F` in the input range, and output them if there are any, and otherwise move on to `(i+1)!`.

Test case:

```
>> f([157, 249])
[162, 192, 216, 243]

```
> 5 votes

# Answer
## C,  ~~149~~  95

**Edited answer:**

I cannot claim credit for this solution. This updated answer borrows the beautiful method used by *isaacg* in his Python solution. I wanted to see if it was possible to write it in C as a nested `for`/`while` loop with no curly braces, and it is!

```
R(a,b,n,q,p,m){for(;a<b;m=p<q?a:m,q=p<q?p:q,n=++a,p=2)while(n>1)if(n%p)p++;else n/=p;return m;}

```

**Explanation:**

* Function `R(a,b,n,q,p,m)` scans the range `a` to `b-1` and returns the first smoothest number found. Invocation requires adherence to the following form: `R(a,b,a,b,2,0)` so that variables inside the function are effectively initialized as follows: `n=a;q=b;p=2;m=0;`.

---

**Original answer**:

This was my original answer...

```
P(n,f,p){for(;++f<n;)p=p&&n%f;return p;}
G(n,f){for(;--f>1;)if(n%f==0&&P(f,1,1))return f;}
R(a,b,p,n){for(;++p;)for(n=a;n<b;n++)if(G(n,n)==p)return n;}

```

**Explanation:**

* Function `P(n,f,p)` tests value `n` for primality and returns true (nonzero) if `n` is prime or false (zero) if `n` is non-prime. `f` and `p` must both be passed as 1.
* Function `G(n,f)` returns the greatest prime factor of `n`. `f` must be passed as `n`.
* Function `R(a,b,p,n)` scans the range `a` to `b-1` and returns the first smoothest number found. `p` must be passed as 1. `n` can be any value.

**Test driver:**

```
test(a,b){printf("smooth_range(%d, %d)\n%d\n",a,b,S(a,b,1,0));}
main(){test(5,11);test(9,16);test(9,17);test(157,249);test(2001,2014);}

```

**Output:**

```
smooth_range(5, 11)
8
smooth_range(9, 16)
9
smooth_range(9, 17)
16
smooth_range(157, 249)
162
smooth_range(2001, 2014)
2002

```
> 4 votes

# Answer
# Haskell - 120

```
import Data.List
import Data.Ord
x!y=(minimumBy(comparing(%2)))[x..y]
x%y|x<y=y|x`mod`y==0=(x`div`y)%y|otherwise=x%(y+1)

```

Example usage:

```
> 5 ! 10
8
> 9 ! 15
9
> 9 ! 16
16
> 157 ! 248
162
> 2001 ! 2013
2002

```
> 4 votes

# Answer
## Q, 91 characters K, 78 characters

```
{(x+{where x=min x}{(-2#{x div 2+(where 0=x mod 2_til x)@0}\[{x>0};x])@0}'[(x)_til y+1])@0}

```

k would probably shave a dozen characters

edit: indeed, treating the upper bound as non inclusive this time

```
{*:x+{&:x=min x}{*:-2#{6h$x%2+*:&:x={y*6h$x%y}[x]'[2_!x]}\[{x>0};x]}'[(x)_!y]}

```
> 4 votes

# Answer
# Note: This answer is not allowable.

This answer uses multiple features of Pyth added after the challenge was asked.

I added another new feature, calling unary range on a 2 element tuple, which shortens the solution by two characters, to this:

# Pyth, 7

```
hoePNUQ

```

Input is now taken comma separated. The rest is the same.

---

This answer uses a feature of Pyth that was added after this question was asked, specifically after seeing @aditsu's wonderful CJam solution. That being said, I wanted to demonstrate what adding that feature has made possible. The feature is `P`, which is an arity-1 function which on integer input returns a list of all prime factors of the input, sorted smallest to largest.

# Pyth, 9

```
hoePNrQvw

```

Uses Python-style ranges, newline separated on STDIN. Outputs smallest solution to STDOUT.

**Explanation:**

```
      Q = eval(input())                         Implicit, because Q is present.
h     head(                                     First element of
 o         order_by(                            Sort, using lambda expression as key.
                    lambda N:                   Implicit in o
  e                          end(               Last element of
   PN                            pfact(N)),     List containing all prime factors of N.
  r                 range(                      Python-style range, lower inc, upper exc.
   Q                      Q,                    A variable, initialized as shown above.
   vw                     eval(input()))))      The second entry of the range, same way.

```

**Tests:**

```
$ newline='
'

$ echo "9${newline}16" | ./pyth.py -c 'hoePNrQvw'
9

$ echo "9${newline}17" | ./pyth.py -c 'hoePNrQvw'
16

$ echo "157${newline}249" | ./pyth.py -c 'hoePNrQvw'
162

$ echo "2001${newline}2014" | ./pyth.py -c 'hoePNrQvw'
2002

```
> 4 votes

# Answer
# Lua - 176 characters

```
a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d==0 do table.insert(f, d)n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

```

I really should stop golfing in Lua. There's no point.
> 3 votes

# Answer
## Clojure - 173 170 chars

I'm a Clojure newbie. Golfed:

```
(defn g[x,d](if(and(= 0(mod x d))(.isProbablePrime(biginteger d) 1))d 0))(defn f[i](apply max-key(partial g i)(range 2(inc i))))(defn s[a,b](first(sort-by f(range a b))))

```

Sample runs:

Ranges include low-end, exclude high-end: \[a,b) Only prints one of the smoothest numbers, if multiple occur.

```
(println (s 5 11))
(println (s 9 16))
(println (s 9 17))
(println (s 157, 249))
(println (s 2001, 2014))

```

yields:

```
bash$ java -jar clojure-1.6.0.jar range.clj
8
9
16
192
2002

```

Ungolfed:

```
(defn g [x,d] (if (and (= 0(mod x d)) (.isProbablePrime (biginteger d) 1)) d 0))
(defn f [i] (apply max-key (partial g i) (range 2 (inc i))))
(defn s [a,b] (first (sort-by f (range a b))))

```
> 3 votes

# Answer
## C# LINQ: ~~317~~ ~~303~~ ~~289~~ 262

```
using System.Linq;class P{static void Main(string[]a){System.Console.Write(Enumerable.Range(int.Parse(a[0]),int.Parse(a[1])).Select(i=>new{i,F=F(i)}).Aggregate((i,j)=>i.F<j.F?i:j).i);}static int F(int a){int b=1;for(;a>1;)if(a%++b<1)while(a%b<1)a/=b;return b;}}

```

Ungolfed:

```
using System.Linq;

class P
{
  static void Main(string[]a)
  {
    System.Console.Write(
      Enumerable.Range(int.Parse(a[0]), int.Parse(a[1])) //create an enumerable of numbers containing our range (start, length)
        .Select(i => new { i, F = F(i) }) //make a sort of key value pair, with the key (i) being the number in question and the value (F) being the lowest prime factor
        .Aggregate((i, j) => i.F < j.F ? i : j).i); //somehow sort the array, I'm still not entirely sure how this works
  }
  static int F(int a)
  {
    int b=1;
    for(;a>1;)
      if(a%++b<1)
        while(a%b<1)
          a/=b;
    return b;
  }
}

```

It takes in the start and the length from the command line and will return the largest smooth number.

I used answers from here and here to make my answer.

Thanks to VisualMelon for tweaking it and shaving 12 bytes off! I also got rid of the braces in the if saving 2 bytes, and CodeInChaos pointed out some obvious stuff I missed (thanks again).
> 3 votes

# Answer
# Ruby, ~~65~~ 62

```
require'prime'
s=->a,b{(a..b).min_by{|x|x.prime_division[-1]}}

```

With apologies to https://codegolf.stackexchange.com/a/36484/6828, this is the golfed (and slightly simplified) version of that. Uses an inclusive range since it's a character shorter.

```
1.9.3-p327 :004 > s[157,249]
 => 192
1.9.3-p327 :005 > s[5,11]
 => 8
1.9.3-p327 :006 > s[9,15]
 => 12
1.9.3-p327 :007 > s[9,16]
 => 16

```

And thanks to YenTheFirst for saving three characters.
> 3 votes

# Answer
## R, 83

```
library(gmp)
n=a:b
n[which.min(lapply(lapply(lapply(n,factorize),max),as.numeric))]

```

where the bottom of the input range is assigned to `a` and the top (inclusive) is assigned to `b`.

`gmp` is a package that is available on CRAN. It felt dirty until I saw that absurd `mf` function in CJam. Install by typing `install.packages("gmp")` in the console.
> 2 votes

# Answer
## PowerShell - 85

```
($args[0]..$args[1]|sort{$d=2
while($_-gt1){while(!($_%$d)){$m=$d;$_/=$d}$d++}$m})[0]

```

This will sort a range of numbers (inclusive) based on each number's max prime factor. It returns the lowest sorted element.

```
> smooth 5 10
8
> smooth 9 15
12
> smooth 9 16
16
> smooth 157 248
243
> smooth 2001 2013
2002

```
> 2 votes

# Answer
# J - 16 char

Using the (*start*, *length*) style of range, as allowed by the comments.

```
(0{+/:{:@q:@+)i.

```

To be used as a dyadic verb: left argument is *start*, right is *length*.

```
   5 (+)i. 6              NB. range
5 6 7 8 9 10
   5 (q:@+)i. 6           NB. prime factorizations
5 0 0
2 3 0
7 0 0
2 2 2
3 3 0
2 5 0
   5 ({:@q:@+)i. 6        NB. largest prime factors
5 3 7 2 3 5
   5 (+/:{:@q:@+)i. 6     NB. sort range by smallest factors
8 6 9 5 10 7
   5 (0{+/:{:@q:@+)i. 6   NB. take first entry
8
   f=:(0{+/:{:@q:@+)i.    NB. can also be named
   2001 f 13
2002

```

A (*start*, *end*) solution is +2 chars, and excludes the end; including the end is +2 more. But on the bright side, it looks rather nice since we match up all the {braces}.

```
(0{}./:{:@q:@}.)i.    NB. excluding
(0{}./:{:@q:@}.)1+i.  NB. including

```
> 2 votes

# Answer
## Seriously, 8\*14/7 = 16 (non-competitive)

```
,x;`yM`M;m@í@E

```

Seriously was created after this challenge, but I wanted to post this answer because it exemplifies the type of challenges Seriously is good at.

Try it online!

Explanation:

```
,x;`yM`M;m@í@E
,x;             make two copies of range(a,b) (a,b = input())
   `  `M;       make two copies of the result of the map:
    yM            push maximum prime factor
         m@í    push index of minimum element from prime factors
            @E  push element from range with given index

```
> 2 votes

# Answer
# Pyth, 7 bytes

```
.mePbrF

```

Try it here!

Outputs all smooth integers in the range \\$\[a, b)\\$. For the smooth integers in \\$\[a, b\]\\$, just use `}` in place of `r`.

```
.mePbrF – Full program with arguments a and b.
     rF – Fold by half-inclusive range. Yields the integers in [a, b).
.m      – Values b in that list which give minimal results when applied f.
  ePb   – function / block f.
   Pb   – Prime factors of b.
  e     – Last element. This is guaranteed to yield the largest, as they're sorted.

```
> 2 votes

# Answer
# Whispers v2, 183 bytes

```
> Input
> Input
>> 1…2
>> ∤L
>> L’
>> Each 4 3
>> Select∧ 5 L
>> Each 7 6
>> Lⁿ10
> -1
>> Each 9 8
>> L‖R
>> Each 12 11 3
>> 13ᴺ
>> Each 9 14
> 0
>> 15ⁿ16
>> Output 17

```

Try it online!

Aside from revamping the algorithm, the only real golfing opportunity can be found on lines **9** and **10**, but swapping them. When they're the other way round, the code is 1 byte longer, due to the repeated use of `9` or `10`.

The structure tree for this program is:

Red represents nilad lines, green represents function arguments. Arrows from \\$a \to b\\$ show the use of line \\$a\\$ as an argument for line \\$b\\$.

## How it works.

We start at lines **1**, **2** and **3**. The first two simply take and store the inputs \\$\alpha\\$ and \\$\beta\\$ on lines **1** and **2** respectively. There two values are then passed to line **3**, `1…2`, which form the range

$$R := \[\alpha, \alpha+1, ..., \beta-1, \beta\]$$

As you can see from the tree above, \\$R\\$ is used in two places: line **6** and line **13**. As line **6** eventually leads to line **13**, we'll take the path down **6**.

Line **6** is an `Each` statement, that maps a function (the first line reference) over an array (the second line reference). Here, the function is defined on line **4** as \\$f(x) = \\{i \\: | \\: (i | x), (i \le x), i \in \mathbb{N}\\}\\$ i.e. the array of \\$x\\$'s divisors. The array is \\$R\\$, so line **6** iterates over \\$R\\$, returning the divisors of each integer, forming a new array

$$D := \[f(\alpha), f(\alpha+1), ..., f(\beta-1), f(\beta)\]$$

We then get more complicated as we skip down to line **8**. Line **8** is also an `Each` statement, but its function argument, line **7** is split over two lines, **7** and **5**:

```
>> L’
>> Select∧ 5 L

```

Mathematically, this is the function \\$g(A) = \\{i \\: | \\: (i \in \mathbb{P}), (i \in A)\\}\\$, that takes a set \\$A\\$ and returns all the primes in \\$A\\$. Line **8** is iterating over \\$D\\$, essentially filtering all composite numbers from each subarray in \\$D\\$, to form

$$A := \[g(f(\alpha)), g(f(\alpha+1)), ..., g(f(\beta-1)), g(f(\beta))\]$$

Then, we encounter yet another `Each` statement on line **11**, which iterates line **9** over \\$A\\$. Line **9** takes an array and returns the final element of that array. As \\$g(A)\\$ returns the array sorted, this is equivalent to return the largest value in that array. At this point, we remember that \\$g(f(x))\\$ returns the list of prime factors of \\$x\\$, so line **9** maps each \\$x\\$ to its largest prime factor, returning

$$B := \[\max(g(f(\alpha))), \max(g(f(\alpha+1))), ..., \max(g(f(\beta-1))), \max(g(f(\beta)))\]$$

Once we have \\$B\\$, we now have an array we can sort \\$R\\$ by, e.g. we sort each value \\$x\\$ in \\$R\\$ by the resulting value of \\$\max(g(f(x)))\\$. However, we do not have a sort-by command in Whispers, only the simple Python `sort(list)`. Luckily, due to how `sort` sorts lists of lists, we can concatenate each \\$x\\$ with \\$\max(g(f(x))\\$ and sort by the first element, what Python does naturally.

Lines **12** and **13** perform this concatenation, by iterating a concatenate function (line **12**) over \\$B\\$ and \\$R\\$. This forms an array of pairs of numbers, in the form \\$\[\max(g(f(x))), x\]\\$. Next, we sort this array on line **14**, which, due to the way Python compares lists, places the numbers with the lowest largest prime factor towards the end.

Almost finished. The only things left to do are to extract \\$R\\$, sorted by \\$B\\$ (we'll call this array \\$R\_B\\$. This is done simply by taking the last element of each subarray (line **9** already does this for us, so we simply need `Each 9 14` on line **15**, rather than defining a new function). Once that's done, we simply take the first element in \\$R\_B\\$, which will be (one of) the number with the lowest largest prime factor i.e. the smoothest number.
> 2 votes

# Answer
# Brachylog, 5 bytes

```
⟦₃ḋᵒh

```

Try it online!

Takes input as a list of two (or more, actually) values in no particular order, and outputs a single value through the output variable of the predicate (if you try to run it as a full program, it'll just print `true.` at you, unless you stick a `w` on the end). The input is interpreted as a Python-style range because to feed  multiple values I need to give it a subscript no matter whether it's , , or  so I may as well choose the one that matches the test cases.

```
    h The first item of
⟦₃    the range represented by the input
   ᵒ  after it's been sorted by
  ḋ   prime factorization.

```

Saves three bytes over the more obvious `⟦₃{ḋh}ᵒh` by taking advantage of that Brachylog sorts its lists by elements first rather than lengths, such that the first step of sorting by prime factorizations is sorting by largest prime factors.
> 2 votes

# Answer
# Husk, 5 bytes = 5.71 characters

```
◄o▲p…

```

Try it online!

**How?**

```
◄       # element that minimizes result of
 o      # combining these 2 functions:
  ▲     # maximum of
   p    # prime factors
    …   # for the range from arg 1 ... arg 2

```
> 2 votes

# Answer
# Cobra - 150

```
def f(r as vari int)
    x,y=r
    c,o=y,0
    for n in x:y,for m in n:0:-1
        p=1
        for l in 2:m,if m%l<1,p=0
        if n%m<=0<p
            if m<c,c,o=m,n
            break
    print o

```

Not even sure why I bothered, cobra just can't compete here.
> 1 votes

# Answer
# Ruby - 113 chars

Using the stdlib. Returns one result. Tested on ruby 2.1.2.

```
require 'prime'
def smooth_range(a,b)
  (a...b).sort_by{|e|e.prime_division.flat_map{|f,p|[f]*p}.uniq.max}[0]
end

```
> 1 votes

# Answer
## Perl (5.10+), 83

```
for(<>..<>){$n=$_;$p=2;$_%$p&&$p++or$_/=$p while$_>1;$m=$p,$r=$n if$p<$m||!$m}
say$r

```

(linebreak can be removed). Takes two endpoints of an inclusive range on two lines of stdin (because `<>` is cheaper than accessing `ARGV`) and outputs the smoothest to stdout. If there's a tie for smoothest, prints the smallest. Could print the biggest at the cost of one character.

The algorithm is basically isaacg's way of finding the greatest prime factor, although we came up with it independently. That part golfs down beautifully to a single statement in perl, the rest has more overhead than I'd like though.

Should be run under `perl -E` or with a `use 5.012` preamble. If you can't do that, replace `say$r` with `print$r,$/`.
> 1 votes

# Answer
# Python 2 (84)

```
f=lambda n,p=2:n>1and f(n/p**(n%p<1),p+(n%p>0))or p
print min(range(*input()),key=f)

```

@isaacg's solution, but with a `min` by function key in place of explicit min-finding, and a recursive function playing the role of the iteration.

Run in Stackless Python to avoid recursion limits.

It looks wasteful to use the paranthesized condition `(n%p<1)`, then repeat its negation also in parantheses `(n%p>0)`, but that was the best I got. I tried things a bunch of things, but they turned out worse.

```
f(n/p**(n%p<1),p+(n%p>0))     # Current for comparison
f(*[n/p,n,p,p+1][n%p>0::2])
n%p and f(n,p+1)or f(n/p,p)
f(*n%p and[n,p+1]or[n/p,p])

```

I welcome any improvements you can think of.
> 1 votes

# Answer
## Java 8 - 422 454 chars

I'm learning Java 8, and wanted to give this a shot relative to Java (or even Java 8 streams).

Compared to other languages, this is brutal but an interesting exercise.

Golfed:

```
import java.util.stream.*;import java.math.*;
class F{int v;int i;public int getV() { return v; }
F(int i){this.i = i;v=IntStream.range(2,i+1).map(j->((i%j==0)&&new BigInteger(""+j).isProbablePrime(1))?j:0).max().getAsInt();}}
public class T{
int s(int a, int b){return IntStream.range(a,b+1).boxed().map(F::new).sorted(java.util.Comparator.comparingInt(F::getV)).collect(java.util.stream.Collectors.toList()).get(0).i;}}

```

Ungolfed:

```
import java.util.stream.*;
import java.math.*;

class F {
    int v;
    int i;
    public int getV() { return v; }
    F (int i) {
        this.i = i;
        v = IntStream.range(2,i+1)
                     .map( j -> ((i%j==0) &&
                           new BigInteger(""+j).isProbablePrime(1))?j:0)
                     .max()
                     .getAsInt();
    }
}

public class T {
    int s(int a, int b) {
        return IntStream.range(a,b+1)
                    .boxed()
                    .map(F::new)
                    .sorted(java.util.Comparator.comparingInt(F::getV))
                    .collect(java.util.stream.Collectors.toList())
                    .get(0).i;
    }
}

```

example run using:

```
public static void main(String[] s) {
    System.out.println(new T().s(157,249));
}

192

```
> 1 votes

# Answer
# MATL (*non-competitive*), 20 bytes

*This language was designed after the challenge*

Range is inclusive at both ends. The numbers are taken as two separate inputs.

```
2$:t[]w"@YfX>v]4#X<)

```

**Try it online!**

### Explanation

```
2$:          % implicitly input two numbers. Inclusive range
t            % duplicate
[]           % empty array
w            % swap elements in stack
"            % for each
  @          %   push loop variable
  Yf         %   prime factors
  X>         %   maximum value
  v          %   vertical concatenation
]            % end for each
4#X<         % arg min
)            % index with this arg min into initial range of numbers

```
> 1 votes

# Answer
# Jelly, 7 bytes, score = 7÷7×8 = 8, language postdates challenge

```
rÆfṀ$ÐṂ

```

Try it online!

Takes the lower and upper range endpoints as two separate arguments. Outputs a list of all the smoothest numbers in the range. (This can be viewed as a function, in which case the output is a Jelly list, or as a full program, in which case the output happens to use the same list representation that JSON does.)

## Explanation

Those times when your Jelly program is just a literal translation of the spec…

```
rÆfṀ$ÐṂ
r        Range from {first argument} to {second argument}
     ÐṂ  Return the elements which have the minimum
   Ṁ$      largest
 Æf          prime factor

```
> 1 votes

# Answer
# 05AB1E, 6 bytes

Input as a list of two items, outputs just one found integer in the `[A,B]` range (inclusive on both sides):

```
ŸΣfθ}н

```

Try it online or verify all test cases.

**Explanation:**

```
Ÿ          # Create a list in the inclusive range of the (implicit) input
           #  i.e. [9,15] → [9,10,11,12,13,14,15]
 Σ  }      # Sort it by:
  f        #  Get the prime factors
           #   i.e. 9 → [3]
           #   i.e. 10 → [2,5]
   θ       #  Pop and push the last item
           #   i.e. [3] → 3
           #   i.e. [2,5] → 5
           #  i.e. [9,10,11,12,13,14,15] → [9,12,10,15,14,11,13]
     н     # After sorting, pop and push the first item
           #  i.e. [9,12,10,15,14,11,13] → 9
           # (and output the result implicitly as result)

```

---

**8 bytes** alternative with same input-format, but outputs all found integers (as string) instead of one:

```
ŸDf€θWQÏ

```

Try it online or verify all test cases.

**Explanation:**

```
Ÿ          # Create a list in the inclusive range of the (implicit) input
           #  i.e. [9,15] → [9,10,11,12,13,14,15]
 D         # Duplicate this list
  f        # Get the prime factors of each
           #  i.e. [9,10,11,12,13,14,15] → [[3],[2,5],[11],[2,3],[13],[2,7],[3,5]]
   €θ      # Only leave the last value of each inner list
           #  i.e. [[3],[2,5],[11],[2,3],[13],[2,7],[3,5]] → [3,5,11,3,13,7,5]
     W     # Get the minimum of this list (without popping the list itself)
           #  i.e. [3,5,11,3,13,7,5] → 3
      Q    # Check for each value in the list if it is equal to this minimum
           #  i.e. [3,5,11,3,13,7,5] and 3 → [1,0,0,1,0,0,0]
       Ï   # Leave only the values of the duplicated list at the truthy indices
           #  i.e. [9,10,11,12,13,14,15] and [1,0,0,1,0,0,0] → ["9","12"]
           # (and output the result implicitly as result)

```
> 1 votes

# Answer
# Factor \+ `math.primes.factors`, 37 bytes

```
[ [a,b) [ factors last ] infimum-by ]

```

Try it online!

## Explanation:

This is a quotation (anonymous function) that takes two integers from the data stack as input and leaves one integer on the data stack as output. Assuming `2001 2014` is on top of the data stack when this quotation is called...

* `[a,b)` Create a range object from two integers. The lower bound is included but the upper bound is excluded. **Stack:** `T{ range f 2001 13 1 }`
* `[ factors last ]` Push a quotation to the data stack to be used later by the `infimum-by` word. **Stack:** `T{ range f 2001 13 1 } [ factors last ]`
* `infimum-by` Apply a quotation to each element of a sequence, returning the element whose result is smallest. (Inside the quotation now...) **Stack:** `2001`
* `factors` Get the sorted list of prime factors given an integer. **Stack:** `{ 3 23 29 }`
* `last` Get the last element of a sequence. **Stack:** `29`
* Now `infimum-by` takes note of `29` and moves onto the next element in its input range...
> 1 votes

# Answer
# Vyxal, 5 bytes

```
ṡ‡ǐt∵

```

Try it Online!

```
ṡ     # Range from a to b
    ∵ # Minimum by...
 ‡--  # Next two as function
   t  # Last
  ǐ   # Prime factor

```
> 1 votes

# Answer
# C#, ~~240~~ ~~234~~ ~~226~~ 161 characters

```
int S(int i,int b){int s=2<<29,n=0,k,j,p;for(k=i;i<b;k=++i){for(;k>1;--k){if(i%k<1){p=1;for(j=2;j<k;++j)if(k%j<1)p=0;if(p>0)break;}}if(k<s){s=k;n=i;}}return n;}}

```

**Acknowledgements & Reduction Explanations**
\- Thanks to CodesInChaos for reductions to 226, see comments for specifics
\- Reduced to 161 after re-reading the rules and seeing that a mere function is allowed (i.e., a free-standing program is not required.)

**Usage**
function:
\- input: two integers
\- output: if multiple valid answers exist, returns the smallest

**Explanation (with comments and runnable test-wrapper)**

```
class Test
{
    int S(int i, int b)
    {
        //s = lowest gpf found so far
        //n = best answer so far
        //i = range iterator
        //p = prime indicator (1=true, 0=false)
        int s = 2 << 29, n = 0, k, j, p;
        for(k=i; i<b; k=++i)
        {
            //iterate through the factors of i
            for(;k>1;--k)
            {
                if (i % k < 1)
                {
                    p=1;
                    //determine if k is prime
                    for (j = 2; j < k; ++j)
                        if (k % j < 1)
                            p = 0;
                    if (p>0) break;
                }
            }
            if (k < s)
            {
                s = k;
                n = i;
            }
        }
        return n;
    }

    public static void Main(string[] args)
    {
        var d = new D();
        System.Diagnostics.Debug.Assert(d.S(5, 11) == 8);
        System.Diagnostics.Debug.Assert(d.S(9, 16) == 9);
        System.Diagnostics.Debug.Assert(d.S(9, 17) == 16);
        System.Diagnostics.Debug.Assert(d.S(157, 249) == 162);
        System.Diagnostics.Debug.Assert(d.S(2001, 2014) == 2002);
    }
}

```
> 0 votes

# Answer
# Japt `-g`, 8 bytes

```
õV ñ_k Ì

```

Try it

---

## Explanation

```
             :Implicit input of integers U & V
õV           :Range [U,V]
   ñ_        :Sort by passing each through a function
     k       :  Prime factors
       Ì     :  Last element
             :Implicitly output the first element in that array

```
> 0 votes

# Answer
# Julia, 58 bytes

```
using Primes
!r=[r;][indmin(max(factor(Set,n)...)for n=r)]

```

Takes a `Range` object of the form `5:9` as input, returns the smallest of the smoothest numbers in the range. (No TIO link, because TIO doesn't seem to have the `Primes` package.)
> 0 votes

# Answer
# Charcoal, 44 bytes

```
Ｎθ≔…θＮη≔¹ζＷ¬№η¹«≦⊕ζＷ⊙η¬﹪λζＵＭη⎇﹪λζλ÷λζ»Ｉ⁺θ⌕η¹

```

Try it online! Link is to verbose version of code. Takes input as a half-open range and returns the lowest smoothest number from that range. Works by trial division of all the numbers in the range until at least one has become completely factorised (in which case it is the smoothest). Explanation:

```
Ｎθ

```

Input the lower end of the range.

```
≔…θＮη

```

Create an array covering the whole range.

```
≔¹ζ

```

Set the initial factor to 1.

```
Ｗ¬№η¹«

```

Repeat until there is at least one `1` in the array.

```
≦⊕ζ

```

Increment the factor.

```
Ｗ⊙η¬﹪λζ

```

Repeat while at least one element is divisible by the factor.

```
ＵＭη⎇﹪λζλ÷λζ»

```

Divide all divisible elements by the factor.

```
Ｉ⁺θ⌕η¹

```

Look up the (first) index of the `1`, add on the lower end of the range, and print the result as a string.
> 0 votes

# Answer
# ECMAScript 2016 - 100 characters

```
m=>M=>(r=_=>M-m?[m,...r(++m)]:[])().sort((x,y)=>(s=(n,p=2)=>n>p?n%p?s(n,p+1):s(n/p,p):p)(x)-s(y))[0]

```

Definitely gets hurt by the lack of a built-in range.

This is a pretty standard anonymous function. It takes in a minimum (inclusive) and a maximum (exclusive), and then spits out the smallest smoothest number in that range.
> 0 votes

# Answer
# MathGolf, 9 bytes

```
↨áæ─g¶╙0§

```

Try it online!

## Explanation

Could be 1-2 bytes shorter with a "get prime factorization" operator.

```
↨           pop a, b, loop from a to b (inclusive)
 á          sort by comparator
  æ         start block of length 4
   ─        get divisors
    g       pop a, (b), pop operator from code, filter
     ¶      is_prime(n)
      ╙     maximum of two elements, max of list, maximum by filter
       0    push 0
        §   get from array

```
> 0 votes

# Answer
# Stax, 9 bytes

```
üwπ┼♦Σjô≤

```

Run and debug it

Thought this would be shorter.
> 0 votes

# Answer
# Thunno 2 `h`, 4 bytes

```
IÞfG

```

Try it online!

#### Explanation

```
IÞfG  # Implicit input
I     # Range between the inputs
 Þ    # Sorted by the following:
  f   #  Prime factors of the number
   G  #  Take the maximum of this list
      # Implicit output of first item

```
> 0 votes

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


title: Implement the iOS 11 Calculator

text:
# Question
Title: Implement the iOS 11 Calculator
iOS 11 has a bug that makes the result of 1+2+3 to be 24. This is related to the animation speed, but anyway:

The task is to make `1 + 2 + 3 == 24`. But only that. So you should provide a function that correctly sums most sequences but returns `24` when the arguments are `1`, `2` and `3` in any order.

Example inputs:

```
1 2 => 3
3 4 => 7
1 2 3 4 5 6 7 8 9 => 45
3 2 1 => 24
2 1 3 => 24
1 1 => 2
1 2 3 => 24
40 2 => 42
1 2 2 4 => 9
1 2 3 4 1 2 3 => 16
1 => 1
1 23 => 24
0 1 2 => 3
3 2 3 => 8

```

Input can be in any format as long as your code accepts any number of arguments.

* Support for negative numbers isn't required (all non negative numbers are required to work, that includes 0)
* We assume correct input

---

Differences from another similar question: "What do you get when you multiply 6 by 9? (42)":

* In this case your function is required to accept **any** number of arguments. The old question specifies exactly 2.
* In this case order doesn't matter, while the old question specified that order `6 9` is required and `9 6` should be evaluated correctly.

# Answer
# Java 8, ~~109~~ ~~106~~ ~~101~~ ~~90~~ ~~75~~ ~~74~~ ~~71~~ 66 bytes

```
a->{int s=0,p=0;for(int i:a){s+=i;p|=1<<i;}return s<7&p==14?24:s;}

```

-12 bytes thanks to *@OlivierGrégoire*.
-31 bytes thanks to *@Nevay*.

**Explanation:**

Try it here.

```
a->{                  // Method with integer-array parameter and boolean return-type
  int s=0,            //  Sum-integer, starting at 0
      p=1;            //  Product-integer, starting at 1
  for(int i:a){       //  Loop over the input-array
    s+=i;             //   Add current item to sum
    p|=1<<i;          //   Take 1 bitwise left-shifted with `i`, and bitwise-OR it with `p`
  }                   //  End of loop
  return p==14        //  If `p` is now exactly 14 (`0b1110`)
    &s<7?             //  and the sum is 6 or lower:
     24               //   Return 24
    :                 //  Else:
     s;               //   Return the sum
}                     // End of method

```

(Inefficient) proof that only `[1,2,3]` (in any order) will be the possible results when `p` is `0b1110` (`p==14`) and the sum is below 6 or lower (`s<7`): **Try it here.**

> `p==14` (`0b1110`) evaluates to true iff the input values modulo 32 cover the values `1`, `2` and `3` and contain no other values (`p|=1<<i`) (each value has to occur 1+ times). The sum of input that matches `p==14` will be larger than `6` for any input except `1,2,3` (`s=a*1+b*2+c*3+u*32` with `a>0,b>0,c>0,u>=0`).
> <sub>*@Nevay*</sub>

---

Old **71 bytes** answer:

```
a->{int s=0,p=1;for(int i:a){s+=i;p*=i;}return a.length==3&p==s?s*4:s;}

```

Proof that for any three given non-zero natural numbers, only `[1,2,3]` (in any order) will have a sum equal to its product (`1+2+3 == 1*2*3`) (with a positive sum):
*When the sum equals the product* by Leo Kurlandchik & Andrzej Nowicki

(Inefficient) proof that only `[1,2,3]` (in any order) and `[0,0,0]` will be the possible results with non-negative numbers and a length of 3: **Try it here.**
So `s*4` will becomes `6*4 = 24` for `[1,2,3]`, and `0*4 = 0` for `[0,0,0]`.
> 12 votes

# Answer
# 05AB1E, 9 bytes

```
Os{3LQi4*

```

Explanation:

```
Os{         Get the sum of the input, and then get the sorted input list
     Qi     If it is equal to...
   3L       [1, 2, 3]
       4*   Then multiply the sum by four.

```

Try it online!
> 11 votes

# Answer
# MATL, ~~11~~ 10 bytes

```
St3:X=6*+s

```

Try it online! or verify all test cases

**Explanation**

```
        % implicit input [3,1,2]
S       % sort
        % STACK: [1,2,3]
t       % duplicate elements
3:      % push range 1..3
        % STACK: [1,2,3], [1,2,3], [1,2,3]
X=      % true if arrays are numerically equal
        % STACK: [1,2,3], 1
6*+     % multiply result of comparison by 6 and add to the original array
        % STACK: [7,8,9]
s       % sum
        % (implicit) convert to string and display

```
> 11 votes

# Answer
# Jelly, 8 bytes

```
3R⁼Ṣ4*×S

```

Try it online!
> 7 votes

# Answer
# MATL, 13 bytes

```
stGp=18*Gda*+

```

Try it online!

It's two bytes longer than the other MATL answer, but it uses a completely different (and IMO more interesting) approach, so I figured it's worth posting.

### Explanation:

This solution uses the fact that:

> The sum and product of an array with three elements are only equal if the array is a permutation of `1,2,3`.

This takes the input, calculates the sum `s`, and duplicates it `t`. It then checks if the sum equals the product `Gp=`. We multiply the boolean `1/0` by 18, `18*`, and checks if there are non-identical values in the vector `da*` (again, multiply by a boolean `any(diff(x))`. We then multiply the two add the last number to the original sum.

A step by step explanation:

Assume the input is `[1, 2, 3]`:

```
s                              % Implicit input, calculate the sum
                               % 6
 t                             % Duplicate the sum:
                               % 6, 6
  G                            % Grab input
                               % 6, 6, [1,2,3]
   p                           % Calculate the product
                               % 6, 6, 6
    =                          % Check if the last two elements are equal
                               % 6, 1 (true)
     18*                       % Push 18, multiply by the last number
                               % 6, 18
        G                      % Grab input
                               % 6, 18, [1,2,3]
         d                     % Calculate the difference between each element
                               % 6, 18, [1,1]
          a                    % any non zero elements?
                               % 6, 18, 1 (true)
           *                   % Multiply last two numbers
                               % 6, 18
            +                  % Add numbers. Result: 24

```
> 7 votes

# Answer
# Haskell, 37 bytes

```
f[a,b,c]|2^a+2^b+2^c==14=24
f l=sum l

```

Try it online!

We use pattern matching to catch the exceptional case.

Haskell doesn't have sorting built-in. The equality `2^a+2^b+2^c==14` is satisfied only by `[a,b,c]` a permutation of `[1,2,3]` among non-negative integers. A shorter `a+b+c=a*b*c` almost works, but is satisfied by `[0,0,0]`, and appending the check `,a>0` makes it 1 byte longer.
> 7 votes

# Answer
# Python 2, 39 bytes

```
lambda*a:sum(a)+18*(sorted(a)==[1,2,3])

```

Try it online!

Uses an alternate method of adding 18 if the sorted input is `[1, 2, 3]` to beat the other Python answer by a byte.
> 6 votes

# Answer
# Octave, 34 bytes

```
@(x)sum(x)+isequal(sort(x),1:3)*18

```

Try it online!

or

```
@(x)(s=sum(x))+18*~(s-6|prod(x)-6)

```

Try it online!

or

```
@(x)(s=sum(x))+18*~(s-prod(x)|s-6)

```

This is shorter than the approach others use: `@(x){24,sum(x)}{2-isequal(sort(x),1:3)}`.

**Explanation:**

It takes the sum of the vector, and adds 18 if the sorted vector is equal to `1,2,3`. This will give `6+18=24` if the vector is a permutation of `1,2,3`, and just the sum of the vector if not.
> 4 votes

# Answer
# PHP, 116 bytes

This is my first attempt at a golfing challenge ever, AND it's PHP, a language which apparently sucks at golfing since I rarely see it here, so ... uhm, I tried?

```
<?php
//call as var/www/html/cg_ios.php --'1 2 3 4 5'
$i=$argv[1];$a=(explode(' ',$i));echo((($b=array_sum($a))==6&&count($a)==3&&in_array(3,$a)&&!in_array(0,$a)?24:$b));

```

Note: I did not include the comment into the bytecount.

### Ungolfed

It's nothing special tbh:

```
$i=$argv[1];             //Read the input from the command line
$a=array_filter($c=explode(' ',$i)) //Split the input string into an array, use Whitespace as delimiter
                         //also, remove all 0 from the array, since they are not important at all
echo(                    //print the result
    ($b=array_sum($a) == 6  //If The SUM of the Array is 6 ...
        &&               //... AND ...
    (count($c) == 3)     //... the array has exactly 3 values ...
        &&               //... AND ...
    in_array(3,$a)       // ... the array contains the value 3 ...
        &&               // ... AND ...
    !in_array(0,$a)      //... the array contains no zeros
        ?
    24                   //print 24
        :
    $b));     //print the sum of the array values we saved earlier

```

If you want to test this in PHPFiddle and not on console, you can obviously replace `$i` with anything you'd like.

Thanks to Olivier Grégoire who made me aware of the string combination `[0,3,3]` which returned 24 before and also helped me saving a few chars by storing the `array_sum` and returning that instead of running the function again.
> 4 votes

# Answer
# R, ~~47 bytes~~ ~~34 bytes~~ 36 bytes

```
x=scan();all(sort(x)==1:3)*18+sum(x)

```

Try it online!

Sum the input and add 18 if the input set is 1:3.
Thanks to @mlt for golfing off 11 bytes. Thanks to @Ayb4btu for identifying an error with the overgolfed code
> 4 votes

# Answer
# Javascript ES6, 39 bytes

Thanks to @Herman Lauenstein

```
a=>a.sort()=="1,2,3"?24:eval(a.join`+`)

```

```
f=a=>a.sort()=="1,2,3"?24:eval(a.join`+`)

console.log(f([1,2,3]));
console.log(f([1,2,3,4]));
```

# Previous answer

Javascript ES6, 66 bytes

```
a=>(n=[1,2,3],a.every(_=>n.includes(_))?24:a.reduce((x,y)=>x+y,0))

```

## Try it

```
f=a=>(n=[1,2,3],a.every(_=>n.includes(_))?24:a.reduce((x,y)=>x+y,0))

console.log(f([1,2,3]));
console.log(f([1,3,2]));
console.log(f([1,2,3,4]));
```
> 3 votes

# Answer
## Swift, 67 Bytes

```
func z(i: [Int])->Int{return i.sorted()==[1,2,3] ?24:i.reduce(0,+)}

```

Could make it to 27 bytes with extensions on \[Int\], but that would be cheating :(
> 3 votes

# Answer
# Mathematica, 28 bytes

```
If[Sort@#=={1,2,3},24,Tr@#]&

```

Try it online!
> 2 votes

# Answer
# Lua, ~~116~~ 81 bytes

-7 bytes thanks to Jonathan

Takes input as command line arguments

```
Z=0S={}for i=1,#arg do
j=arg[i]+0S[j]=0Z=Z+j
end
print(#S>2 and#arg<4 and 24or Z)

```

Try it online!

# Explanation:

Works by creating an sparse array `S` and adding zeroes in the indices corresponding to the input values. If parameters are `3, 4, 7` the sparse array will only have numbers at those indices. With that array, we get it's length with the operator `#` that counts from index `1` up to the higher index that has a value in it, if this length is exactly `3`, it means that there were elements in the position `1`, `2` and `3` wich is what we're looking for. The length of the sparse array will be always between `0` and `N` where `N` is the number of parameters. So we just have to check if the length of both the parameters array and the sparse array is `3`.
> 2 votes

# Answer
# , ~~55~~ ~~45~~ ~~54~~ ~~49~~ ~~57~~ ~~54~~ 48 bytes

Saved many ~~bytes and~~ incorrect solutions thanks to Ayb4btu.

Saved ~~3~~ 9 bytes thanks to Giuseppe. I keep learning new ways to abuse the fact that `F==0`.

```
"if"((s=sum(x<-scan()))-prod(x)|sum(x|1)-3,s,24)

```

Try it online!

The other R answer won in the end.
> 2 votes

# Answer
# J, 17 bytes

*-6 bytes thanks to Frowny Frog*

```
+/*1+3*1 2 3-:/:~

```

Sum all the numbers `+/` and multiply the result by (pseudocode) `1 + 3*(is123 ? 1 : 0)`. That is, return the results unchanged unless the sorted list is `1 2 3` in which case we multiply the result by 4.

Try it online!

### original answer

```
+/`(24"_)@.(1 2 3-:/:~)

```

Check if the sorted input is `1 2 3` -- if yes, invoke the constant function 24 (`24"_`); if not, return the sum `+/`

Try it online!
> 2 votes

# Answer
# C (gcc), ~~136~~ ~~131~~ ~~125~~ ~~97~~ ~~91~~ ~~83~~ 81 bytes

Thanks to @landfill babby, and @ceilingcat (of course we're not using c anymore)

```
r,t;main(i,v)int**v;{for(;*++v;t|=1<<i)r+=i=atoi(*v);printf("%d",r>6|t-14?r:24);}

```

Try it online!
> 2 votes

# Answer
# C# (.NET Core), 57+18=75 bytes

```
a=>a.OrderBy(x=>x).SequenceEqual(new[]{1,2,3})?24:a.Sum()

```

Try it online!

+18 for `using System.Linq;`
> 2 votes

# Answer
# C++17, ~~56~~ 54 bytes

```
[](auto...i){return(-i&...)+4|(~i*...)+24?(i+...):24;}

```

Try it online!

Note that the function object created is usable at compile time, so the tests are performed by the compiler without having to run a program.

### Explanation:

```
[]             // Callable object with empty closure,
(auto...i)     // deduced argument types,
{              // and deduced return type
  return       //
      (-i&...) //   If the fold over the bitwise AND of the negation of each argument
    +4|        // is unequal to -4, or
      (~i*...) //   if the product of the bitwise complements of the arguments
    +24?       // is unequal to -24, then
      (i+...): //   return the sum of the arguments, otherwise
      24;}     //   return 24.

```

Proof that the only nonnegative `i...` for which `(-i&...)` equals -4 and `(~i*...)` equals -24 are the permutations of `1, 2, 3`:

We first observe that since `-0` = `0`, if any `i` = `0` then `(-i&...) = 0`, so we conclude that all the `i` are positive.

Now, note that in 2's complement, `-i` is equivalent to `~(i - 1)`, and `~i` is equivalent to `-(i + 1)`. Applying De Morgan's rule, we find that `(-i & ...)` = `~((i - 1) | ...)` = `-(((i - 1) | ...) + 1)`, so `((i - 1) | ...) = 3`; similarly, `-1 ** n * ((i + 1) * ...) = -24`, so `n` is odd and `((i + 1) * ...) = 24`.

The prime factors of 24 are 2\**3 * 3, so `n` \<= 4. If `n` = 1, we have `i - 1 = 3` and `i + 1 = 24`, so `n` = 3. Write the `i` wlog as `a <= b <= c`, then clearly `a` = 1 as otherwise `(a + 1)(b + 1)(c + 1)` \>= 27. Also `c` \<= 4 as otherwise `(a - 1)|(b - 1)|(c - 1)` \>= 4. `c` cannot be 4 as 5 is not a factor of 24, so `c` \<= 3. Then to satisfy `(a - 1)|(b - 1)|(c - 1) = 3` c = 3, b = 2 as required.
> 2 votes

# Answer
## Retina, 21 bytes

```
O`
^1¶2¶3$
24
.+
$*
1

```

Try it online!

Input is linefeed-separated, but the test suite uses comma-separation for convenience.

### Explanation

```
O`

```

Sort the numbers (lexicographically, actually, but we only care about the case that the inputs are `1`, `2`, `3` in some order, where that doesn't make a difference).

```
^1¶2¶3$
24

```

If the input is `1,2,3` (in some order), replace it with 24.

```
.+
$*

```

Convert each number to unary.

```
1

```

Count the number of `1`s, which adds the unary numbers and converts them back to decimal.
> 1 votes

# Answer
# Haskell, 44 bytes

```
f a|sum a==6,product a==6,a<[6]=24|1<2=sum a

```

Try it online!

The permutations of `[1,2,3]` are the only partitions of `6` whose product is `6`, barring `6` itself. (This assumes the inputs are non-negative, which seems to be the case for all the test cases… I’ve asked the OP about this.)
> 1 votes

# Answer
## **PL/SQL - ~~135~~ 123 Bytes**

Assuming i as an integer array input of any size:

```
if (select sum(s) = exp(sum(ln(s))) from unnest(i) s) then
    return 24;
else
    return (select sum(s) from unnest(i) s);
end if;

```
> 1 votes

# Answer
# Husk, 9 bytes

```
?K24Σ=ḣ3O

```

Try it online!

### Explanation

```
?K24Σ=ḣ3O
        O    Sort the input
?    =ḣ3     If it is equal to [1,2,3]:
 K24           Return 24
             Else:
    Σ          Return the sum of the input

```

### Previous solution

Gives the wrong result to \[2,2\], and probably other inputs too, but it was more interesting.

```
?ṁD→E§eΠΣ
     §eΠΣ    Build a two-element list with the product and sum of the input
?   E        If the two elements are equal:
             (true for any permutation of [1,2,3] and the list [0,0,0]
 ṁD            Double both elements and sum them
               (This is 4 times the sum: 24 for permutations of [1,2,3], 0 for [0,0,0])
             Else:
   →          Return the last element (the sum)

```

Try it online!
> 1 votes

# Answer
# Jq 1.5, 35 bytes

```
if[1,2,3]==sort then 24else add end

```

Assumes input is an array e.g. `[2,1,3]`

Try it online!
> 1 votes

# Answer
# Jelly, ~~10~~ 9 bytes

```
Ṣ24S⁼?3R¤

```

Try it online!

-1 byte thanks to Erik

Alternative (by Mr. Xcoder), also for 9 bytes:

```
3R⁼Ṣ×18+S

```

Try it online!

## How it works

```
Ṣ24S⁼?3R¤ - Main link. Argument: l (list)

Ṣ         - Sort
     ?    - Ternary if statement
    ⁼     -  Condition: Is l equal to...
      3R¤ -    [1, 2, 3]
 24       -  If condition: Return 24
   S      -  Else: Return the sum of the list

```
> 0 votes

# Answer
# Python 2, ~~41~~ 39 bytes

-1 byte thanks to caird

-1 by inspiration from FlipTack's answer

```
lambda*a:sum(a)*4**(sorted(a)==[1,2,3])

```

Try it online!

### Alternative 39 bytes solution

```
lambda*a:sum(a)<<2*(sorted(a)==[1,2,3])

```
> 0 votes

# Answer
# APL (Dyalog), ~~20~~ 15 bytes

*5 bytes saved thanks to @EriktheOutgolfer*

```
{4*⍵[⍋⍵]≡⍳3}×+/

```

Try it online!
> 0 votes

# Answer
# Pushy, 12 bytes

```
gF3RFx?18;S#

```

Try it online!

This works by sorting the input and, if it is equal to `[1, 2, 3]`, appending 18. Then, the sum is calculated and printed, yielding 24 is 18 was appended, and the normal answer otherwise.

```
         \ Implicit: Input on stack.
g        \ Sort input ascendingly
F3RF     \ On auxiliary stack, push range(3) -> [1, 2, 3]
x?       \ If the stacks are equal:
  18     \    Append 18 to the input
;
S#       \ Print sum of input.

```
> 0 votes

# Answer
# Haskell, 47 bytes

```
import Data.List
f l=sum$l++[18|sort l==[1..3]]

```

Try it online!
> 0 votes

# Answer
# Pyth, 9 bytes

```
?qS3SK24s

```

**Verify all the test cases.**
> 0 votes

# Answer
# Pyth, 9 bytes

Different aproach from the other Pyth answer.

```
*sQ^4qS3S

```

### Explanation:

A port from my Python answer

```
*sQ^4qS3SQ  # Full program (Q at the end is implicit and represents the input)

*           # A * B where A and B are the next two lines
  sQ        # Sum elements of input
  ^4        # 4 to the power of:
    qS3SQ   # Compares sorted input to [1, 2, 3] and returns 0 or 1

```

Try it online!
> 0 votes

# Answer
# PowerShell, 44 bytes

```
param($a)($a-join'+'|iex)+18*!(diff(1..3)$a)

```

Try it online!

Similar algorithm to the Python and JavaScript answers. Takes input as a literal array `$a`. Then immediately sums `$a` together, which forms the left-hand operator of the `+`.

The right-hand is the `diff` (alias for `Compare-Object`) of `1,2,3` and `$a` -- this is either an empty array if they are equal, or a non-empty array of the different items if they are not equal -- enclosed in a Boolean-not. So, if they are equal, that makes the empty array (a falsey value) into `$true`.

That's then multiplied by `18` which implicitly casts `$true` to `1` and `$false` to `0`. So the right-hand side will be `18` if the arrays are the same, and `0` otherwise. That gives the correct result of `24` if the input array is `1,2,3` in any permutation, and the summation of the input array otherwise.
> 0 votes

# Answer
# Kotlin, ~~46~~ 44 bytes

```
if(i.sorted()==listOf(1,2,3))24 else i.sum()

```

Try it online!

# Edits
> 0 votes

# Answer
# C++, 109 bytes

```
#import<list>
int f(std::list<int>l){l.sort();int s=0;for(int i:l)s+=i;return l==std::list<int>{1,2,3}?24:s;}

```

Try it online!
> 0 votes

# Answer
# Japt `-x`, ~~14~~ 11 bytes

```
n e3õ)?24:U

```

Try it online!
> 0 votes

# Answer
# Perl 5, 25 bytes

```
[sort@_]~~[1..3]?24:sum@_

```

Try it online!
> 0 votes

# Answer
# Racket, 49 bytes

```
(λ x(if(equal?(sort x <)'(1 2 3))24(apply + x)))

```

Try it online!
> 0 votes

# Answer
# Perl 5, 34 bytes

```
[sort@_]~~[1..3]?24:0+map{1..$_}@_

```

Try it online!

This is similar to my other answer, but does not use the import `sum` function. Instead it creates an array whose size is the sum of the number. But only works for non-negative integers.
> 0 votes

# Answer
# Ruby, 29 bytes

```
->a{a.sort==[*1..3]?24:a.sum}

```
> 0 votes

# Answer
# C (gcc), ~~111~~ 153 bytes

```
#define A(x)if(v[x]>v[x+1]&c>2)t=v[x],v[x]=v[x+1],v[x+1]=t;
i;s;t;f(c,v)int*v;{for(s=i=0;i<c;s+=v[i++]);A(0)A(1)A(0)return c!=3|*v-1|v[1]-2|v[2]-3?s:24;}

```

Try it Online!

+42: Fixed {3,2,3}, {1,1,1}, {2,2,2}, etc.

I will try to golf more later.

`f` is a function which takes the length of the array as an `int` and a pointer to the first element of the array (of `unsigned int`s) and returns the 'IOS 11 Calculator Sum' of the array.

Ungolfed (Old, broken version):

```
#define not_one_two_or_three(index) (arr[index] > 3 || arr[index] == 0)
int counter;
int sum;
int ios_sum(int length, unsigned int *arr) {
    sum = 0;
    for (counter = 0; counter < length; counter++) {
        sum += arr[counter];
    }
    if (length != 3 || not_one_two_or_three(0) || not_one_two_or_three(1) || not_one_two_or_three(2))
        return sum;
    else return 24;
}

```
> 0 votes

# Answer
# q/kdb+, 24 bytes

**Solution:**

```
(sum x;24)1 2 3~x:asc(),

```

Try it online!

**Note:** Link is to a K (oK) port of the K4 version below as there is no TIO for q/kdb+.

**Examples:**

```
q)(sum x;24)1 2 3~x:asc(),1
1
q)(sum x;24)1 2 3~x:asc(),1 2
3
q)(sum x;24)1 2 3~x:asc(),1 2 3
24
q)(sum x;24)1 2 3~x:asc(),1 2 3 4
10
q)(sum x;24)1 2 3~x:asc(),1 3 2
24

```

**Explanation:**

q is interpreted right-to-left:

```
(sum x;24)1 2 3~x:asc(), / the solution
                     (), / convert to list if not already a list (cannot sort atom)
                  asc    / sort list ascending
                x:       / store input in variable x
          1 2 3~         / is sorted list equal to list 1 2 3? boolean 0 or 1
(     ;  )               / two item list which we index into
       24                / index 1 (true), the fake result 24
 sum x                   / index 0 (false), sum the input list

```

**Notes:**

* K4 version that aligns with TIO link: `(+/x;24)1 2 3~x@<x:(),` for 22 bytes
* Q is just syntactic sugar on top of K4, `sum` is `+/`, `asc` is `x@<x`
> 0 votes

# Answer
# Ruby, 28 bytes

`->s{s&[*1..3]==s&&24||s.sum}`
> 0 votes

# Answer
# Add++, 17 bytes

```
L,dB#3R=''1$o$b+*

```

Try it online!
> 0 votes

# Answer
# Thunno 2 `S`, 8 bytes

```
ṠD3R⁼6×+

```

Try it online!

#### Explanation

```
ṠD3R⁼6×+  # Implicit input
ṠD        # Sort and duplicate
  3R⁼     # Equals [1,2,3]?
     6×+  # Multiply by 6 and add
          # Implicit output of sum

```
> 0 votes

# Answer
# Racket, 52 bytes

```
(define(c x)(if(equal?(sort x <)'(1 2 3))24(sum x)))

```

Try it online!

---

## Explanation

We create a function called `c` that checks whether `x` is equal to `'(1 2 3)` when `x` is sorted. If it is, we return `24`, otherwise we take the sum of the list.

```
(define (calc xs)
  (if (equal? (sort xs <) '(1 2 3))
      24
      (sum xs)))

```
> 0 votes

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


title: Fibonacci reversed!

text:
# Question
Title: Fibonacci reversed!
## Introduction

We all know and love our Fibonacci sequence and have seen a myriad of challenge on it here already. However, we're still lacking a very simple case which this answer is going to provide: Reversed fibonacci! **So given `F_n` your job is to find `n`.**

## Specification

### Input

Your input will be a non-negative integer, which is guaranteed to be part of the fibonacci sequence.

### Output

The output must be a non-negative integer as well.

### What to do?

The introduction already said: Given a fibonacci number, output its index. Fiboancci number hereby is defined as `F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)` and you're given `F(n)` and must return `n`.

### Potential Corner Cases

0 is a valid in- and output.
If given "1" as input you may either output "1" or "2", as you prefer.
You may always assume that your input actually is a fibonacci number.
You may assume that the input is representable as a 32-bit signed integer.

### Who wins?

This is code-golf so the shortest answer in bytes wins!
Standard rules apply of course.

## Test-cases

```
0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46

```

# Answer
> 62 votes
## Actually, 1 byte

```
f

```

Yes, there's a builtin for this, since November 16, 2015.

Try it online

---

For fun, without the builtin, it's 9 bytes:

```
╗1`F╜=`╓i

```

Try it online!

Explanation:

```
╗1`F╜=`╓i
╗          push input to register 0
 1`F╜=`╓   push list containing first value x (starting with x = 0) where:
   F         fib(x)
    ╜=       is equal to the input
        i  flatten the list

```

# Answer
> 44 votes
# Mathematica, 25 bytes

```
InverseFunction@Fibonacci

```

Function. Pretty self-explanatory if you ask me.

# Answer
> 32 votes
# Python, ~~36~~ ~~34~~ 32 bytes

```
lambda n:len(str(66*n**6))//1.24

```

### Previous versions:

```
f=lambda n:len(str(66*n**6))//1.24
f=lambda n:(n*n*7).bit_length()//1.4

```

## Explanation

The core idea is to invert the formula

```
fibonacci(n) ~ ( (1 + sqrt(5)) / 2)**n / sqrt(5)

```

which tells us that

```
log fibonacci(n) ~ n log((1 + sqrt(5)) / 2) - log(sqrt(5))

```

to get

```
f(n) ~ (log(n) + log(sqrt(5))) / log((1 + sqrt(5))/2)

```

The golfing optimizations are:

* Use `len(str(n))` to compute log base 10 without importing `log` (old version used `.bit_length()` to compute log base 2)
* Raise `n` to a power, so that the approximation of the logarithm can distinguish between successive Fibonacci numbers
* Multiplying by a constant scales up the values to get them in the correct range

Then the divisor was truncated to as little precision as I could manage and the multiplier chosen to give the correct results for all 32-bit fibonacci numbers.

# Answer
> 19 votes
# 05AB1E, 3 bytes

Code:

```
ÅFg

```

Explanation:

```
ÅF   # Generate all Fibonacci numbers <= input.
  g  # Get the length of this list.

```

Uses the **CP-1252** encoding. Try it online!.

# Answer
> 16 votes
# Julia, ~~27~~ ~~26~~ 18 bytes

```
!n=log(3n+.7)÷.48

```

This uses the inverse of Binet's formula, with just enough precision for 32-bit integers; it actually works up to **F(153) = 42,230,279,526,998,466,217,810,220,532,898 \> 2105**.

Try it online!

### How it works

Binet's formula states the following.

Restricting **F** to the set of Fibonacci, the map **n → Fn** has a right inverse **F → nF**.

We have that

and all that is left to do is dealing with the edge case **0**.

Since the input is restricted to 32-bit integers, we can use short decimal literals instead of the constants in the formula.

* **log φ = 0.481211825059603447… ≈ 0.48**

Unfortunately, **0.5** isn't precise enough.
* **√5 = 2.2360679774997896964… ≈ 3**

That might seem like an awful approximation at first glance, but we're taking logarithms and since **log 3 - log √5 = 0.29389333245105…**, the result before rounding will be off by a small constant factor.
* **0.5 ≈ 0.7**

Because of the excess from the previous approximation, we could actually omit this term altogether and still get correct results for **F \> 0**. However, if **F = 0**, the logarithm will be undefined. **0.7** turned out to be the shortest value that extends our formula to **F = 0**.

# Answer
> 9 votes
# Jelly, ~~14~~ 11 bytes

```
5½×lØp+.Ḟ»0

```

Try it online!

This is my first ever Jelly answer! This uses the algorithm from the MATL answer. Thanks to Dennis for shaving off 3 bytes!

Explanation:

```
   lØp      # Log Base phi
5½          # Of the square root of 5
  ×         # Times the input
      +     # Plus
       .    # 0.5
        Ḟ   # Floored

```

This gets the right answer, now we just need to handle the special case of '0'. With '0' as an arg, we get `-infinity`, so we return

```
»      # The maximum of
 0     # Zero
       # And the previous calculated value.

```

# Answer
> 8 votes
# JavaScript, ~~54~~ ~~50~~ ~~69~~ ~~50~~ 42 bytes

```
b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c

```

Surely it isn't going to win, just for fun :)

~~Ok, checking for zero consumes 19 bytes. WTF?~~ Stupid-me.

---

Demo! To see the last test case, you have to scroll the console a bit.

```
a=b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c;
console.log('0: '+a(0));
console.log('2: '+a(2));
console.log('3: '+a(3));
console.log('5: '+a(5));
console.log('8: '+a(8));
console.log('13: '+a(13));
console.log('1836311903: '+a(1836311903));
```

Thanks @edc for shortening by 8 bytes.

# Answer
> 8 votes
# Perl 6  ~~33 30~~  27 bytes

```
~~{first *==$_,:k,(0,1,*+*...*>$_)}
{first *==$_,:k,(0,1,*+*...*)}~~
{first $_,:k,(0,1,*+*...*)}
```

Try it

### Explanation:

```
# lambda with implicit ｢$_｣ parameter
{
  first           # find the first element
    $_,           # where something is equal to the block's argument
    :k,           # return the key rather than the value

    # of the Fibonacci sequence
    ( 0, 1, * + * ... * )
    # ^--^ first two values
    #       ^---^ lambda used to generate the next in the series
    #             ^-^ generate until
    #                 ^ Whatever
}

```

### Test:

```
#! /usr/bin/env perl6
use v6.c;
use Test;

# using the safer version that stops generating
# values bigger than the input
my &fib-index = {first $_,:k,(0,1,*+*...*>$_)}

my @tests = (
  0 => 0,
  2 => 3,
  3 => 4,
  5 => 5,
  8 => 6,
  13 => 7,
  1836311903 => 46,
  1836311904 => Nil, # this is why the safe version is used here
  12200160415121876738 => 93,
  19740274219868223167 => 94,
  354224848179261915075 => 100,
);

plan +@tests + 1;

for @tests -> $_ ( :key($input), :value($expected) ) {
  cmp-ok fib-index($input), &[eqv], $expected, .gist
}

cmp-ok fib-index((0,1,*+*...*)[1000]), &[eqv], 1000, 'works up to 1000th element of Fibonacci sequence'

```

```
1..13
ok 1 - 0 => 0
ok 2 - 2 => 3
ok 3 - 3 => 4
ok 4 - 5 => 5
ok 5 - 8 => 6
ok 6 - 13 => 7
ok 7 - 1836311903 => 46
ok 8 - 1836311904 => Nil
ok 9 - 12200160415121876738 => 93
ok 10 - 19740274219868223167 => 94
ok 11 - 354224848179261915075 => 100
ok 12 - works up to 1000th element of Fibonacci sequence

```

# Answer
> 7 votes
# Jelly, 8 bytes

```
1+Ð¡0
¢i

```

Try it online! Note that this approach is too inefficient for the last test case.

### How it works

```
¢i     Main link. Argument: n

¢      Call the helper link niladically (i.e., without arguments).
       This yields the sequence of the first n positive Fibonacci numbers, i.e.,
       [1, 1, 2, 3, 5, ...].
 i     Find the first index of n (1-based, 0 if not found).

1+Ð¡0  Helper link. No arguments.

1      Set the left argument to 1.
    0  Yield 0.
 +Ð¡   Add both arguments, replacing the left argument with the sum and the right
       argument with the previous value of the left argument.
       Yield the array of all intermediate values of the left argument.

```

# Answer
> 6 votes
## Pyke, 5 bytes

```
.f.bq

```

Try it here!

```
.f    - first number where
  .b  -  fib(n)
    q - ^ == input

```

# Answer
> 6 votes
## Python, 29 bytes

```
g=lambda n:n>.7and-~g(n/1.61)

```

Recursively divides the input by the golden-ratio approximation 1.61 until it's below 0.7, and outputs the number of divisions.

For 0, the code outputs `False`, which equals 0 in Python. This can be avoided for 2 bytes

```
g=lambda n:n//.7and 1+g(n/1.61)

```

# Answer
> 4 votes
# MATL, 14 bytes

```
t?5X^*17L&YlYo

```

**Try it online!**

This uses an inverse of Binet's formula, and so it's very fast.

Let *F* denote the *n*-th Fibonacci number, and *φ* the golden ratio. Then

The code uses this formula with two modifications:

* Instead of adding 1/2 and then rounding down, the code simply rounds towards the nearest integer, which takes up fewer bytes.
* Input *F*=0 needs to be treated as a special case.

### How it's done

```
t         % Take input F implicitly. Make a copy
?         % If (copy of) F is positive
  5X^     %   Push sqrt(5)
  *       %   Multiply by F
  17L     %   Push phi (predefined literal)
  &Yl     %   Two-input logarithm: first input is argument, second is base
  Yo      %   Round towards nearest integer
          % Else the input, which is 0, is left on the stack
          % End if implicitly
          % Display implicitly

```

# Answer
> 4 votes
## Sage, 49 bytes

```
lambda x,s=sqrt(5):x and int(log(x*s,(1+s)/2)+.5)

```

Thanks to TuukkaX for the suggestion about saving `sqrt(5)` as `s` to shave off a few bytes.

Try it online.

This approach using an inverse of Binet's formula offers several improvements over the previous approach: it's faster (constant-time versus quadratic time), it actually works for larger inputs, and it's shorter!

Python users may wonder why I'm using `sqrt(5)` instead of the shorter `5**.5` \- it's because `5**.5` is computed with C's `pow` function, and loses precision due to floating point issues. Many mathematical functions (including `sqrt` and `log`) are overloaded in Sage to return an exact, symbolic value, which don't lose precision.

# Answer
> 4 votes
## JavaScript (ES6), ~~39~~ 33 bytes

```
f=(n,j=0,k=1)=>n>j?f(n,k,j+k)+1:0

```

Even with ES7, the inverse Binet formula takes 47 bytes:

```
x=>Math.log(x*5**.5)/Math.log(.5+1.25**.5)+.5|0
x=>Math.log(x*5**.5)/Math.log((1+5**.5)/2)+.5|0
x=>Math.log(x*(p=5**.5))/Math.log((1+p)/2)+.5|0

```

# Answer
> 4 votes
## JavaScript, 22 bytes

```
n=>Math.log(n)/.48+2|0

```

# Answer
> 4 votes
# Regex (.NET), ~~23~~ 19 bytes

```
(\2?(\1)|x$|^x|\b)*

```

Try it online!

Takes its input in unary, as a string of `x` characters whose length represents the number. Returns its output as the capture count of group `\1`.

This is based on Martin Ender's .NET regex for matching Fibonacci numbers. The .NET feature of balanced groups is used to count the number of iterations taken by the loop.

* That regex is first initially translated to use `x` as its unary numeral, yielding `^$|^(^x|(?>\2?)(\1))*x$`.
* Then the `x$` at the end is moved inside as the extra alternative `|x$`, incrementing the loop count by \\$1\\$ for all \\$n\>0\\$. This also allows us to remove the `^$|` at the beginning, because `^(^x|(?>\2?)(\1)|x$)*$` will now match \\$n=0\\$ on its own. (It will also now match numbers that are \\$0\\$ or \\$1\\$ less than a Fibonacci number, but we don't care because as specified by the challenge, all inputs will be Fibonacci numbers.)
* Then the extra alternative `|\b` is added to increment the loop count again for all \\$n\>0\\$; `\b` cannot match on an input of \\$n=0\\$ because there is no word character (`[0-9A-Za-z_]`) to form a boundary with the absense of a word character, but it will always match at the end of a string of one or more `x`s. The match is zero-width, so the loop will then be terminated.
* Then we remove the `^` and `$` anchors sandwiching the regex, because we don't need to return a non-match for non-Fibonacci numbers.
* Then an optimization for speed, moving the `^x` alternative as far to the end as possible, because it only has to match once, and would add a failed match to every subsequent iteration if ordered as the first alternative.
* The `\2?` can lose the `(?>`...`)` atomic group around it, because we don't need to determine if a number is Fibonacci or not. Due to the lack of any assertions following the loop, it will simply keep the first match it finds at each iteration, not having any reason to backtrack.

**27 byte** version that matches iff the input is a Fibonacci number:

```
^((?>\2?)(\1)\B|x$|^x|\b)*$

```

Try it online!

The `\B` prevents numbers \\$1\\$ less than a Fibonacci number from being matched; in unary, `\B` matches at every place except the beginning and end in a non-zero number (and matches "everywhere" in an input of zero).

# Regex  (PCRE1 / PCRE2 v10.34 or earlier), 20 bytes

```
^(\2?(\1)|x$|^x)+|^x

```

Try it online! \- PCRE1
Try it online! \- PCRE2 v10.33

Takes its input in unary, as the length of a string of `x`s. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)

This is a straight port of the .NET version to the  output format. It needs to be anchored, so that the only variation in how a match can happen is how many iterations the loop takes, not where in the string it starts. The `*` is changed to `+` because with the former, looping for 0 iterations would still be a match, and would result in a 1-indexed return value.

Moving the `|\b` alternative to the end as `|^x` is a minor speed optimization, at a zero-byte cost. As an added bonus, we can change this to `|^xx` to return \\$1\\$ (instead of \\$2\\$) for an input of \\$1\\$.

For PCRE1, and PCRE2 before v10.35, the atomic group is not needed even with -output, because those versions automatically atomicize groups that contain a nested backreference (in this case, `\1`).

# Regex  (Perl / PCRE), 23 bytes

```
^(\2?+(\1)|^x)+|^x|^xxx

```

Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
Try it online! \- PCRE1
Try it online! \- PCRE2 v10.33 / Attempt This Online! \- PCRE2 v10.40+

Try it online! \- PCRE2 - every Fibonacci number up to \\$F\_{46}\\$ in under 20 seconds

Instead of atomicizing the whole loop, as `^((?>\2?(\1)|x$|^x|\b))+`, we move all choices out of the loop, so there's only one thing it can do at any iteration. This saves 1 byte.

As in the PCRE1 version, we can change `|^x` to `|^xx` to return \\$1\\$ (instead of \\$2\\$) for an input of \\$1\\$.

An alternative 23 byte option would be `^(\2?+(\1)|x$|^x)+|^xxx`, but that'd be ever-so-slightly slower due to having an extra choice inside the loop.

# Regex (.NET), ~~33~~ 29 bytes

```
(?=(^(x)|\3?(\1)|)*)(?<-1>x)*

```

Try it online!

Returns its output as the sum of the lengths of the match (group `\0`) and group `\2`. It is done as a sum because for inputs \\$n=1,2,3\\$ the Fibonacci index is \\$n+1\\$ and would not fit in a single capture group.

Group `\2`, which is `(x)` in this regex, is captured as \\$1\\$ iff the loop takes at least one iteration, which happens for all \\$n\>0\\$. The loop count itself is also given an extra increment, as in the **23 byte** version above, by the addition of an empty alternative `|` inside the loop. This will result in a zero-width match being taken at the end, regardless of input; it even happens for \\$n=0\\$, but that doesn't matter, because the `(?<-1>x)*` will not have room to pop its capture, and the return match will be \\$0\\$ anyway.

Note that this regex would actually *not* be made shorter by returning its output as the sum of the lengths of `\0`, `\3`, and `\3`, as the shortest way I can think of to do that takes **34 bytes**:

```
(?=((?>\2?)(\1)|^x)*(x))?(?<-1>x)*

```

Try it online!

**38 byte** version that matches iff the input is a Fibonacci number:

```
^(?=(^(x)|(?>\3?)(\1)|)*x$|$)(?<-1>x)*

```

Try it online!

# Regex (Perl / PCRE), 31 bytes

```
((?=(\2?x))(^x|\4?+(\3)))*(x|^)

```

Try it online! \- Perl
Try it online! \- PCRE

Returns its output as the sum of the lengths of groups `\2`, `\5`, and `\5`. The regex saves 3 bytes just by using a possessive quantifier, replacing `(?>\4?)` with `\4?+`.

The Fibonacci index minus \\$2\\$ is built up in `\2` using the expression `(?=(\2?x))`. The first time this is hit, the `\2?` will evaluate to zero because `\2` isn't set yet, and `\2` will be given a value of \\$1\\$. On every subsequent iteration, it will be incremented. This is done in a lookahead to avoid influencing the running total Fibonacci match, and is safe because at every step, the index will be less than the amount added to the full match.

The `(x|^)` at the end serves to let `\5`\\$=1\\$ in all cases except \\$n=0\\$.

This regex does not work under Java; group `\2` just captures \\$1\\$ and stays there. This may be due to a bug in Java's regex engine.

**33 byte** version that matches iff the input is a Fibonacci number:

```
^((?=(\2?x))(^x|\4?+(\3)))*(x|^)$

```

Try it online! \- Perl
Try it online! \- PCRE

If the output specification must be simplified to sum only two groups, this would be the shortest way I can think of doing it (**39 bytes**, output is the sum of the lengths of groups `\0` and `\5`):

```
(?=((?=(\2?x))(^x|\4?+(\3)))*(x))?\2?x?

```

Try it online! \- Perl
Try it online! \- PCRE

**42 byte** version that matches iff the input is a Fibonacci number:

```
^(?=((?=(\2?x))(^x|\4?+(\3)))*(x|^)$)\2?x?

```

Try it online! \- Perl
Try it online! \- PCRE

# Answer
> 4 votes
# Prolog (SWI), 90 bytes

*Written in conversation with flawr in chat.*

```
F-N-A-B:-F=A;N>0,M is N-1,C is A+B,F-M-B-C.
F/N/I:-N=I,F-N-0-1;J is I+1,F/N/J.
F/N:-F/N/0.

```

Try it online!

### Ungolfed

Here's a less-golfed version:

```
fib(F,0,F,_).
fib(F,N,A,B) :- N>0, M is N-1, C is A+B, fib(F,M,B,C).
fibindex(F,N,N) :- fib(F,N,0,1).
fibindex(F,N,I) :- J is I+1, fibindex(F,N,J).
fibindex(F,N) :- fibindex(F,N,0).

```

The `fib/4` predicate (`F-N-A-B` in the golfed version) takes a number `N` and two accumulators `A` and `B` (which should start at `0` and `1`) and unifies `F` with the `N`th Fibonacci number. If `N` is `0`, `F` is simply the current value of `A`, the smaller accumulator value. Otherwise, count `N` down by one and recurse with new accumulator values `B` and `A+B`.

`fibindex/3` (`F/N/I` in the golfed version) takes a Fibonacci number `F` and an index `I` (which should start at `0`) and unifies `N` with the Fibonacci index of `F`. Either `F` is the `I`th Fibonacci number, in which case `N=I` and we're done, or we count `I` up by one and recurse. Note that this approach leads to infinite recursion if given a non-Fibonacci number, but we don't have to handle that case for this challenge.

Finally, `fibindex/2` (`F/N`) just calls `fibindex/3` with an initial `I` value of `0`.

# Answer
> 3 votes
# Python, 38 bytes

```
f=lambda n,a=0,b=1:n^a and-~f(n,b,a+b)

```

Test it on Ideone.

# Answer
> 3 votes
# C, 62 58 bytes

```
g(c,a,b){return c-a?g(c,b,a+b)+1:0;}f(c){return g(c,0,1);}

```

**Detailed**

```
int g(int c, int a, int b)
{
    if (c == a)
    {
        return 0;
    }
    else
    {
        return g(c, b, a+b) + 1;
    }
}

int f(c)
{
    return g(c, 0, 1);
}

```

# Answer
> 3 votes
# Java 7, 70 bytes

```
int c(int n){int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;}

```

https://ideone.com/I4rUC5

# Answer
> 2 votes
## TSQL, 143 bytes

Input goes in `@n` as in `DECLARE @n INT = 1836311903;`

```
DECLARE @O BIGINT=0;WITH F(R,P,N)AS(SELECT @O,@O,@O+1 UNION ALL SELECT R+1,N,P+N FROM F WHERE N<=@n)SELECT MAX(R)FROM F OPTION(MAXRECURSION 0);

```

# Answer
> 2 votes
## Haskell, 45 bytes

```
f x=round$log(sqrt 5*x+0.9)/log((sqrt 5+1)/2)

```

# Answer
> 2 votes
# Sesos, 28 bytes

Hexdump:

```
0000000: 16f8be 766ef7 ae6d80 f90bde b563f0 7ded18 3ceffa  ...vn..m.....c.}..<..
0000015: b1c1bb af9f3f ff                                  .....?.

```

Try it online!

(Exponential time because in Sesos copying a number needs exponential time.)

Assembly used to generate the binary file:

```
set numin
set numout
get
jmp
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz    ;input input
fwd 4
add 1  ;input input 0 1
fwd 2
add 1  ;input input 0 1 0 1
rwd 4
jmp
jmp    ;input input-curr curr next iterations
sub 1
jnz    ;input 0 curr next iterations
fwd 3
add 1
jmp
sub 1
fwd 2
add 1
rwd 2
jnz    ;input 0 curr next 0 0 iterations+1
rwd 1
jmp
sub 1
fwd 1
add 1
fwd 1
add 1
rwd 2
jnz    ;input 0 curr 0 next next iterations+1
rwd 1
jmp
sub 1
fwd 1
sub 1
fwd 2
add 1
rwd 3
jnz    ;input 0 0 -curr next curr+next iterations+1
rwd 2
jmp
sub 1
fwd 2
add 1
fwd 1
add 1
rwd 3
jnz    ;0 0 input input-curr next curr+next iterations+1
fwd 3
jnz
fwd 3
put

```

# Answer
> 2 votes
# Java 8 61 bytes

Same as @dainichi answer only made shorter by using Java 8 lambdas. The answer is a valid rvalue expression.

```
n->{int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;}

```

Ungolfed:

```
interface F
{
    int c(int n);
}

public class Main
{

    public static void main(String[] args)
    {
        F f = n->{int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;};
    }
}

```

# Answer
> 2 votes
# Brachylog, 14 bytes

```
≜∧0;1⟨t≡+⟩ⁱ↖?h

```

Try it online!

Takes input through the output variable and outputs through the input variable.

```
≜                 Label the input variable, trying 0, 1, -1, 2...,
  0               then starting with 0
 ∧                (which is not necessarily the input variable)
   ;1             paired with 1,
     ⟨t≡ ⟩        replace the first element of the pair with the last element
     ⟨ ≡+⟩        and the last element of the pair with the sum of the elements
          ⁱ↖?     a number of times equal to the input variable,
             h    such that the first element of the pair is the output variable.

```

I'm not entirely sure why  is necessary.

# Answer
> 2 votes
# APL (Dyalog Extended), 14 bytes

```
(+.!∘⌽⍨∘⍳¨…)⍳⊢

```

Explanation soon (TM)

Try it online!

# Answer
> 2 votes
# Vyxal, ~~6~~ 4 bytes

```
ÞFḟ›

```

Try it Online!

-2 thanks to Deadcode

1 byte longer than it should be just because Vyxal's "Fibonacci sequence" builtin does not start with 0.

# Answer
> 2 votes
# C89 (clang), 54 bytes

```
a,b,r;g(f){for(a=r=0,b=1;a<f;++r)b+=a,a=b-a;return r;}

```

Try it online!

# Answer
> 2 votes
# Japt, 8 bytes

```
ô!gM è<U

```

Try it

## Original, 9 bytes

Can handle larger inputs than the version above.

```
nMgV°)©Òß

```

Try it

# Answer
> 1 votes
# Pyth, 13 bytes

```
J1tf>=Z+~JZZQ

```

Test suite.

Approximation in Python 2:

```
Z=0;J=1;T=1;Q=input()
while not J+Z>Q:
    temp=J
    J=Z
    Z=temp+J
    T += 1
print(T-1)

```

### alternative approach, 18 bytes

```
L?<b2bsyMtBtbs.IyG

```

Test suite.

This uses `.I` for inverse.

# Answer
> 1 votes
# J, ~~32~~ ~~27~~ 17 bytes

```
i.~0,+/@(!|.)\@i.

```

Computes the first *n* Fibonacci numbers and then finds the index of *n* in that list.

## Usage

Extra commands are used for formatting multiple input/output. The last test case is omitted since it will require much more time to compute.

```
   f =: i.~0,+/@(!|.)\@i.
   (,.f"0) 0 1 2 3 5 8 13
 0 0
 1 1
 2 3
 3 4
 5 5
 8 6
13 7

```

## Explanation

```
i.~0,+/@(!|.)\@i.  Input: n
               i.  Get the range [0, 1, ..., n-1]
             \@    For each prefix of that range
          |.         Reverse the prefix
         !           Find the binomial coefficient between each value in the original
                     prefix and the reversed prefix
     +/@             Sum those binomial coefficients
                   This will create the Fibonacci numbers from 1 to n
   0,              Prepend a 0 to the list of Fibonacci numbers
i.~                Find the index of n in that list and return

```

# Answer
> 1 votes
# Java 7, 89 bytes

```
int c(int n){int i=-1;while(f(++i)<n);return i;}int f(int n){return n<2?n:f(n-1)+f(n-2);}

```

Inspired by the explanation of *@Adnan*'s 05AB1E answer.

**Ungolfed & test cases:**

Try it here. (Time limit exceeded for last test case, but it works in about 30-45 seconds on my PC.)

```
class Main{
  static int c(int n){
    int i = -1;
    while(f(++i) < n);
    return i;
  }

  static int f(int n){
    return n < 2
             ? n
             : f(n - 1) + f(n - 2);
  }

  public static void main(String[] a){
    System.out.println(c(0));
    System.out.println(c(2));
    System.out.println(c(3));
    System.out.println(c(5));
    System.out.println(c(8));
    System.out.println(c(1836311903));
  }
}

```

**Output:**

```
0
3
4
5
6
46

```

# Answer
> 1 votes
## Perl 5.10, 48 bytes

Basically looking for the right `n` so that `F(n) = input`.

`-a` switch adds one byte.

```
$b++;while($_>$a){$c=$a;$a+=$b;$b=$c;$n++}say$n

```

Try it here!

# Answer
> 1 votes
# Jelly, 9 bytes

```
‘RḶUc$S€i

```

Finds the first *n*+1 Fibonacci numbers and locates the index of *n* in that list.

Note: This is very inefficient and large test cases should not be run on the online interpreter.

Try it here.

## Explanation

```
‘RḶUc$S€i  Input: n
‘          Increment n
 R         Generate the range [1, 2, ..., n+1]
           For each value x in that range
  Ḷ          Create the range [0, 1, ..., x-1]
   U         Create a reversed copy
    c        Compute the binomial coefficient between each pair of values
     $       Combine the last two links (Uc) as a monad
      S€   Sum each list of binomial coefficients
           This will result in a list of the first n+1 Fibonacci numbers
        i  Find the index of n in that list and return

```

# Answer
> 1 votes
# Mathematica, 30 bytes

```
Round@Log[5^.5/2+.5,.8+5^.5#]&

```

Pure function; returns 2 if the input is 1.

Doesn't beat the other Mathematica entry, but showcases an unusual method: It's a (very cool) fact that the Nth Fibonacci number is the closest integer to \[1/sqrt(5) times the Nth power of the golden ratio\] ("Binet's formula").

Therefore the inverse function will be the base-\[golden ratio\] logarithm of \[sqrt(5) times the Fibonacci number in question\]. The `.8+` is a hack to make sure we don't take the logarithm of 0, without screwing up the other values.

# Answer
> 1 votes
# Groovy, 38 bytes

```
{a=c=0;b=1;for(;a<it;b+=(a=b-a))c++;c}

```

# Answer
> 1 votes
# Japt, 10 bytes

```
Lo æ@U¥MgX

```

Try it online!

## Explanation

```
Lo æ@U¥MgX
Lo           // Creates a range from 0 to 99
   æ@        // Iterates through the range. Returns the first item X where:
     U¥      //   Input ==
       MgX   //   Xth Fibonacci number

```

# Answer
> 1 votes
# Jelly, 5 bytes

```
‘ÆḞ€i

```

Try it online!

Nothing special here, just an updated version of Jelly

## How it works

```
‘ÆḞ€i - Main link. Takes n on the left
‘     - Yield n+1
   €  - For each k = 1, 2, ..., n+1:
 ÆḞ   -   Yield the k'th Fibonacci number
    i - Return the index of n in this list

```

# Answer
> 1 votes
# x86-64 machine code, System V calling convention, 16 bytes

```
31 c0 99 6a 01 59 0f c1 d1 ff c0 39 fa 75 f7 c3

```

In assembly:

```
fib:
    # initialize registers: rax=0, rdx=0, rcx=1
    xor eax,eax
    cdq
    push 1
    pop rcx
fib_loop:
    # add registers and swap over and over
    # until the result equals the input
    xadd ecx,edx
    inc eax
    cmp edx,edi
    jne fib_loop
    ret

```

Try it online!

Explicitly computes the nth Fibonacci number in `ecx` and `edx`, while keeping track of the count in `eax`. Takes input in `rdi` and returns in `rax`, as usual for 64-bit x86.

# Answer
> 0 votes
## Javascript (using external library) (84 bytes)

```
n=>_.Until((i,a)=>{l=a.length;if(a[l-1]!=n){return i<=1?i:a[l-1]+a[l-2]}}).Count()-1

```

Link to lib: https://github.com/mvegh1/Enumerable

Code explanation: Library has static method that creates a sequence until the predicate has an undefined return value. The predicate has a signature of ("i"ndex, current internal "a"rray generated). At each iteration, we check if the last element of the internal array is equal to the input, n. If not, return the next value in the fib sequence. Otherwise, the predicate has an undefined result which terminates the generation of the sequence. Then, we return the length of the sequence (and subtract 1 in order to comply with the 0 based-ness as seen in the OP

# Answer
> 0 votes
# C#, 130 Bytes

Golfed:

```
int F(int n){var a=new int[4];a[1]=1;int i=0;while(a[3]<n){a[3]=a.ToList().GetRange(1,2).Sum();a[1]=a[2];a[2]=a[3];i++;}return i;}

```

Ungolfed:

```
public int F(int n)
{
  var a = new int[4];

  a[1] = 1;

  int i = 0;

  while (a[3] < n)
  {
    a[3] = a.ToList().GetRange(1, 2).Sum();

    a[1] = a[2];
    a[2] = a[3];

    i++;
  }

  return i;
}

```

Test:

```
var fibonacciReversed = new FibonacciReversed();

var fr = fibonacciReversed.F(0);
Console.WriteLine(fr);
0

fr = fibonacciReversed.F(2);
Console.WriteLine(fr);
3

fr = fibonacciReversed.F(3);
Console.WriteLine(fr);
4

fr = fibonacciReversed.F(5);
Console.WriteLine(fr);
5

fr = fibonacciReversed.F(8);
Console.WriteLine(fr);
6

fr = fibonacciReversed.F(13);
Console.WriteLine(fr);
7

fr = fibonacciReversed.F(1836311903);
Console.WriteLine(fr);
46

```

# Answer
> 0 votes
# AWK, 58 bytes

```
{for(n[++j]++;n[j]<$1;n[++j]=n[j]+n[j-1]){}j=$0?j:0;$0=j}1

```

Try it online!

# Answer
> 0 votes
# Factor \+ `project-euler.002`, ~~23~~ 22 bytes

```
[ dup fib-upto index ]

```

Try it online!

# Answer
> 0 votes
# Thunno 2, 4 bytes

```
ĖÆFȮ

```

Try it online!

#### Explanation

```
ĖÆFȮ  # Implicit input
Ė     # Push [0..input] to the stack
 ÆF   # nth Fibonacci number for each
   Ȯ  # Index of input in this list
      # Implicit output

```

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