Indexing the Extended Fibonacci Numbers

Question

You've probably heard of Fibonacci numbers. Ya know, that integer sequence that starts with 1, 1, and then each new number is the sum of the last two?

1 1 2 3 5 8 13...

And so on. Challenges about Fibonacci numbers are pretty popular 'round here. But who says that the Fibonacci numbers have to start with 1, 1? Why couldn't they start with 0, 1? Alright, let's redefine them to start at 0:

0 1 1 2 3 5 8 13...

But... We don't have to stop there either! If we can add the last two numbers to get the next one, we could also subtract the first number from the second number to prepend a new number. So it could start with 1, 0:

1 0 1 1 2 3 5 8 13...

We can even end up with negatives:

-1 1 0 1 1 2 3 5 8 13...

And this series also goes on forever. I think it's interesting how it ends up kinda mirroring the regular Fibonacci numbers, just with every other number made negative:

13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...

Let's call this series the "Extended Fibonacci Number", or EFN. Since there isn't really an obvious negative number to start this series on, we'll say that 0 shows up at 0, the regular Fibonacci numbers extend in to the positive indices, and the negative (half-negative?) Fibonacci numbers extend in to the negative indices, like so:

Indices: ...-7  -6 -5  -4 -3  -2 -1  0  1  2  3  4  5  6  7 ...
Values:  ...13  -8  5  -3  2  -1  1  0  1  1  2  3  5  8  13...

This leads into today's challenge:

Given an integer N, return every index at which N appears in the EFN series.

Some random observations on this task:

• 1 appears more times in the EFN than any other number: [-1, 1, 2]. No number will appear in more than 3 places.

• Every Fibonacci number > 1 will show up either once (3, 8, 21, etc.) or twice (2, 5, 13, etc.)

Rule Clarifications:

• If abs(N) is not a Fibonacci number, it will never appear in the EFN series, so you must output nothing/an empty collection if possible, or if that is not possible in your language, you can output some constant non-numeric value.
• If N appears at multiple places in the EFN, your output does not need to be sorted. Although each index must appear exactly once.
• Although most sequence challenges allow you to choose whether you want to use 1-based or 0-based indexing, this challenge must use the indexing described (where 0 appears at 0).
• You may take I/O through any standard format.

Test Cases

-13: []
-12: []
-11: []
-10: []
-9: []
-8: [-6]
-7: []
-6: []
-5: []
-4: []
-3: [-4]
-2: []
-1: [-2]
0: 0
1: [-1, 1, 2]
2: [-3, 3]
3: [4]
4: []
5: [-5, 5]
6: []
7: []
8: [6]
9: []
10: []
11: []
12: []
13: [-7, 7]

And some larger test cases:

89: [-11, 11]
1836311903: [46]
10000: []
-39088169: [-38]

As usual, shortest answer in bytes wins!

Answer 1

Haskell, 78 bytes

4 bytes saved thanks to nimi

a#b=a:b#(a-b)
f 0=[0]
f a=do{(i,x)<-zip[0..a*a+1]$0#1;[-i|x==a]++[i|abs x==a]}

Try it online!

First we set up (#), (#) takes two parameters, a and b, and returns the a list starting with a and followed by b#(a-b). This creates an infinite list, but because Haskell is lazy we don't need to wory about it looping forever. This essentially works backwards creating the Fibonacci sequence before a certain pair. For example (0#1) would be the list of all the Fibonacci numbers with negative index.

From here we make f. f takes a argument a which is the number we are trying to find in the sequence. Here we use do notation to do a list comprehension. We start by taking the first a*a+1 elements of the list 0#1¹. Since the function a*a+1 grows faster than the inverse of the Fibonacci sequence we can be sure that if we check within this bound we will find all the results. This prevents us from searching an infinite list. Then for each value x and index i, if x==a we found a in the negative half of the sequence so we return -i, and if abs x==a we return i as well because the absolute value of the negative half is the positive half so we found it there.

Since this makes the list [0,0] for 0 we hardcode the correct output for that one.

^{1: This trick is taken from Οurous' Clean answer. The same speedup aplies here as there, replace a*a+1 with abs a+1 to save a lot of time.}

Answer 2

Clean, 132 120 109 bytes

import StdEnv
g n|n<2=n=g(n-1)+g(n-2)
?k=[e\\p<-[0..k*k+1],e<-if(isOdd p)([~p,p]%(0,k))[p*sign k]|g p==abs k]

Try it online!

g :: Int -> Int is the Fibonacci function.
? :: Int -> [Int] just indexes into the elements of the EFN within k^2+1 of 0.

For a version that runs in a sane ammount of time, change k*k+1 to abs k+1.

Answer 3

Jelly, 11 bytes

A‘ŒRÆḞẹ_A_2

Try it online!

Answer 4

JavaScript (ES6),  94  93 bytes

n=>(g=a=>a*a<n*n?g(b,b+=a,i++):a%n)(i=0,b=1)?[]:i&1?n<0?~n?[]:-2:i-1?[-i,i]:[-i,i,2]:n<0?-i:i

Try it online!

Or 92 bytes if we can return \$-0\$ for \$n=0\$.

Answer 5

APL (Dyalog Classic), 52 50 bytes

Requires ⎕IO←0

{X-⍨⍸⍵=F,⍨⌽0,F×1 ¯1⍴⍨≢F←{⍵≤1:1⋄+/∇¨⍵-1 2}¨⍳X←1+|⍵}

Try it online!

Answer 6

Retina 0.8.2, 104 102 bytes

[1-9].*
$*
(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*
-1(11)+$

^1(11)+$
-$&,$&
1+
$.&
^2$
-1,1,2

Try it online! Explanation:

[1-9].*
$*

Convert to unary, unless the input is zero.

(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*

Calculate the Fibonacci index of the absolute value, but if the number is not a Fibonacci number then delete it, unless it was zero. This uses @MartinEnder's Fibonacci-testing regex.

-1(11)+$

Delete negative numbers whose absolute values are odd Fibonacci numbers.

^1(11)+$
-$&,$&

Add negative indices for odd positive Fibonacci numbers.

1+
$.&

Convert to decimal.

^2$
-1,1,2

Add the extra indices for 1.

Answer 7

Actually, 34 bytes

;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░

Brute-force saves the day

Explanation:

;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░
;╗                                  save a copy of the input (let's call it N) to register 0 (the main way to get additional values into functions)
  3*;±                              -3*N, 3*N
      kSi                           push to list, sort, flatten (sort the two values on the stack so that they are in the right order for x)
         x                          range(min(-3*N, 3*N), max(-3*N, 3*N))
          ⌠;;AF@;1&@0>*YτD(s**╜=⌡░  filter (remove values where function leaves a non-truthy value on top of the stack):
           ;;                         make two copies of parameter (let's call it n)
             AF                       absolute value, Fib(|n|)
               @;                     bring a copy of n to the top of the stack and make another copy
                 1&                   0 if n is divisible by 2 else 1
                   @0>                1 if n is negative else 0 (using another copy of n)
                      *               multiply those two values (acts as logical AND: is n negative and not divisible by 2)
                       YτD            logical negate, double, decrement (maps [0, 1] to [1, -1])
                          (s          sign of n (using the last copy)
                            **        multiply Fib(|n|), sign of n, and result of complicated logic (deciding whether or not to flip the sign of the value for the extended sequence)
                              ╜=      push value from register 0, equality comparison (1 if value equals N else 0)

Try it online!

Answer 8

Python 3, 92 bytes

f=lambda x,l=[],i=0,a=0,b=1:i<x*x+2and f(x,l+[i][:a==x]+[-i][:i%2*2*a-a==x],i+1,b,a+b)or{*l}

Try it online!

Returns a set of indices.

Answer 9

Python 2, 87 85 bytes

f=lambda v,a=0,b=1,i=1:v*v>=a*a and[i]*(v==b)+[1-i]*((-1)**i*a==v)+f(v,b,a+b,i+1)or[]

Try it online!

Answer 10

05AB1E, 36 bytes

x*ÝʒÅfIÄQ}Ii®šë1KIdiÐ`ÉiD(ì}ëD`Èi(ë¯

There has to be a better approach.. >.> There are six (or seven if we include 0) different scenarios for this challenge, and it's killing me..

Try it online or verify all test cases.

Explanation:

x*Ý            # Create a list in the range [0, (implicit) input * input * 2]
   ʒ     }     # Filter this list by:
    Åf         #  Where the Fibonacci value at that index
      IÄQ      #  Is equal to the absolute value of the input
Ii             # If the input is exactly 1:
  ®š           #  Prepend -1 to the list
ë              # Else:
 1K            #  Remove all 1s (only applies to input -1)
 Idi           #  If the input is non-negative:
    Ð`Éi   }   #   If the found index in the list is odd:
        D(ì    #    Prepend its negative index to the list
   ë           #  Else (the input is negative):
    D`Èi       #   If the found index in the list is even:
        (      #    Negate the found index
       ë       #   Else (found index is odd):
        ¯      #    Push an empty array
               # (Output the top of the stack implicitly as result)

Some step-by-step examples:

Input:  Filtered indices:  Path it follows (with actions) and result:

-8      [6]                NOT 1 → neg → even index → negate index: [-6]
-5      [5]                NOT 1 → neg → odd index → push empty array: []
-1      [1,2]              NOT 1 → (remove 1) neg → even remaining index: negate index: [-2]
0       [0]                NOT 1 → even index → negate index: [0]    
1       [1,2]              1 → prepend -1: [-1,1,2]
5       [5]                NOT 1 → non-neg → odd index → Prepend neg index: [-5,5]
8       [6]                NOT 1 → non-neg → even index → (nothing): [6]

Answer 11

Python 2, 95 92 94 bytes

x=input()
i=a=0;b=1
while x*x>=a:
 if 0<a==x:print i
 if[-a,a][i%2]==x:print-i
 a,b=b,a+b;i+=1

Try it online!

Answer 12

C# (Visual C# Interactive Compiler), 144 bytes

o=>{int c=0,n=1,i=0,k=Math.Abs(o);for(;c<k;i++,n+=c,c=n-c);return new[]{c>k|o<0?0.1:i,(i>0|o<0)&i%2>0&c==k?-i:0.1,o==1?2:0.1}.Where(p=>p!=0.1);}

Try it online!