14
\$\begingroup\$

The famous Fibonacci sequence is F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1) (for this challenge we are beginning with 0).

Your challenge: Given n, output the sum of all the dth Fibonacci numbers for all divisors d of the nth Fibonacci number. If you prefer more formal notation,

The Sum

Input: a positive integer n

Output: the sum

For example, consider n=4. F(4) = 3The divisors of 3 are 1 and 3, so the output should be F(1) + F(3) = 1 + 2 = 3.

For n=6, F(6) = 8, and the divisors of 8 are 1, 2, 4, 8, so the output is F(1) + F(2) + F(4) + F(8) = 1 + 1 + 3 + 21 = 26.

Test Cases:

1 => 1
2 => 1
3 => 2
4 => 3
5 => 6
6 => 26

This is , shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$

19 Answers 19

2
\$\begingroup\$

Actually, 5 bytes

F÷♂FΣ

Try it online!

How it works

       (implicit) Read n from STDIN.
F      Compute F(n).
 ÷     Get F(n)'s divisors.
  ♂F   Map F over the divisors.
    Σ  Take the sum.
\$\endgroup\$
  • \$\begingroup\$ The name of the language makes it seem passive aggressive, is that intended? \$\endgroup\$ – Rohan Jhunjhunwala May 27 '17 at 21:14
  • 1
    \$\begingroup\$ I doubt it. The first version of the language was called Seriously because of this comment. For the second version, the author chose to keep using adjectives. \$\endgroup\$ – Dennis May 27 '17 at 21:20
6
\$\begingroup\$

Jelly, 7 bytes

ÆḞÆDÆḞS

Try it online!

Explanation:

ÆḞÆDÆḞS Main link (Arguments: z)
ÆḞ      zth Fibonacci number's
  ÆD                           divisors'
    ÆḞ                                   Fibonacci numbers'
      S                                                     sum
\$\endgroup\$
  • \$\begingroup\$ Absolutely outrageous! I don't know any of these exotic languages, but it seems supernatural to me how you can write a whole algorithm with a few characters. \$\endgroup\$ – Bogdan Alexandru May 24 '17 at 13:20
  • \$\begingroup\$ @BogdanAlexandru You can see that most of the builtins used here each consume 2 bytes, since they didn't fit in 1 byte. See Dennis's Actually answer for even fewer chars. Also, Jelly is a "golfing language", a language made specifically for code-golf, and it's one of the most efficient ones here (although there isn't one "most efficient" language). \$\endgroup\$ – Erik the Outgolfer May 24 '17 at 13:28
  • \$\begingroup\$ Are you saying that these languages aren't used in practice and they're only meant for challenges? \$\endgroup\$ – Bogdan Alexandru May 24 '17 at 13:31
4
\$\begingroup\$

Mathematica, 29 bytes

f=Fibonacci;f@#~DivisorSum~f&
\$\endgroup\$
4
\$\begingroup\$

Mathematica Simplified, 14 bytes

Fi@#~Div9`~Fi&

Oh well, this ended up being identical to @MartinEnder's solution...

\$\endgroup\$
  • \$\begingroup\$ Well... Using a shorter version of the same language... I guess that works. \$\endgroup\$ – Neil A. May 23 '17 at 15:03
  • \$\begingroup\$ There are no single letter function names in Mathematica, right? Could you not match all two character strings formed from a leading upper case letter plus a single byte? If so you'd have 26*256=6656 simplified 2-byte function names, enough for the 6356 11.1.1 names with 300 to spare. \$\endgroup\$ – Jonathan Allan May 23 '17 at 16:45
  • \$\begingroup\$ @JonathanAllan Good idea. (but there are single name functions, like N) \$\endgroup\$ – JungHwan Min May 23 '17 at 18:08
3
\$\begingroup\$

Japt, 11 bytes

MgU â x@MgX

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Gah! You beat me to it again! \$\endgroup\$ – Shaggy May 23 '17 at 15:08
  • \$\begingroup\$ @Shaggy you have to get faster ;) \$\endgroup\$ – Tom May 23 '17 at 15:08
2
\$\begingroup\$

05AB1E, 11 bytes

!ÅFDI<èÑ<èO

Try it online!

Explanation

!            # factorial of input
 ÅF          # get the list of fibonacci numbers (starting at 1)
             # smaller than or equal to this
   D         # duplicate list of fibonacci number
    I<è      # get the element at index (input-1)
       Ñ     # get the list of its divisors
        <    # decrement each
         è   # get the fibonacci numbers at those indices
          O  # sum
\$\endgroup\$
2
\$\begingroup\$

Haskell, 54 bytes

f=0:scanl(+)1f
g x=sum[f!!d|d<-[1..f!!x],mod(f!!x)d<1]

Usage example: g 6 -> 26. Try it online!

\$\endgroup\$
2
\$\begingroup\$

Alice, 38 36 bytes

Thanks to Leo for saving 2 bytes.

/ow;B1dt&w;31J
\i@/01dt,t&w.2,+k;d&+

Try it online!

Almost certainly not optimal. The control flow is fairly elaborate and while I'm quite happy with how many bytes that saved over previous versions, I have a feeling that I'm overcomplicating things that there might be a simpler and shorter solution.

Explanation

First, I need to elaborate a bit on Alice's return address stack (RAS). Like many other fungeoids, Alice has a command to jump around in the code. However, it also has commands to return to where you came from, which lets you implement subroutines quite conveniently. Of course, this being a 2D language, subroutines really only exist by convention. There's nothing stopping you from entering or leaving a subroutine through other means than a return command (or at any point in the subroutine), and depending on how you use the RAS, there might not be a clean jump/return hierarchy anyway.

In general, this is implemented by having the jump command j push the current IP address to the RAS before jumping. The return command k then pops an address of the RAS and jumps there. If the RAS is empty, k does nothing at all.

There are also other ways to manipulate the RAS. Two of these are relevant for this program:

  • w pushes the current IP address to the RAS without jumping anywhere. If you repeat this command you can write simple loops quite conveniently as &w...k, which I've already done in past answers.
  • J is like j but doesn't remember the current IP address on the RAS.

It's also important to note that the RAS stores no information about the direction of the IP. So returning to an address with k will always preserve the current IP direction (and therefore also whether we're in Cardinal or Ordinal mode) regardless of how we passed through the j or w that pushed the IP address in the first place.

With that out the way, let's start by looking into the subroutine in the above program:

01dt,t&w.2,+k

This subroutine pulls the bottom element of the stack, n, to the top and then computes the Fibonacci numbers F(n) and F(n+1) (leaving them on top of the stack). We never need F(n+1), but it will be discarded outside the subroutine, due to how &w...k loops interact with the RAS (which sort of requires these loops to be at the end of a subroutine). The reason we're taking elements from the bottom instead of the top is that this lets us treat the stack more like a queue, which means we can compute all the Fibonacci numbers in one go without having to store them elsewhere.

Here is how this subroutine works:

                                                          Stack
01    Push 0 and 1, to initialise Fibonacci sequence.     [n ... 0 1]
dt,   Pull bottom element n to top.                       [... 0 1 n]
t&w   Run this loop n times...                            [... F(i-2) F(i-1)]

  .     Duplicate F(i-1).                                 [... F(i-2) F(i-1) F(i-1)]
  2,    Pull up F(i-2).                                   [... F(i-1) F(i-1) F(i-2)]
  +     Add them together to get F(i).                    [... F(i-1) F(i)]

k     End of loop.

The end of the loop is a bit tricky. As long as there's a copy of the 'w' address on the stack, this starts the next iteration. Once those are depleted, the result depends on how the subroutine was invoked. If the subroutine was called with 'j', the last 'k' returns there, so the loop end doubles as the subroutine's return. If the subroutine was called with 'J', and there's still an address from earlier on the stack, we jump there. This means if the subroutine was called in an outer loop itself, this 'k' returns to the beginning of that outer loop. If the subroutine was called with 'J' but the RAS is empty now, then this 'k' does nothing and the IP simply keeps moving after the loop. We'll use all three of these cases in the program.

Finally, on to the program itself.

/o....
\i@...

These are just two quick excursions into Ordinal mode to read and print decimal integers.

After the i, there's a w which remembers the current position before passing into the subroutine, due to the second /. This first invocation of the subroutine computes F(n) and F(n+1) on the input n. Afterwards we jump back here, but we're moving east now, so the remainder of the program operators in Cardinal mode. The main program looks like this:

;B1dt&w;31J;d&+
        ^^^

Here, 31J is another call to the subroutine and therefore computes a Fibonacci number.

                                              Stack
                                              [F(n) F(n+1)]
;     Discard F(n+1).                         [F(n)]
B     Push all divisors of F(n).              [d_1 d_2 ... d_p]
1     Push 1. This value is arbitrary.        [d_1 d_2 ... d_p 1]
      The reason we need it is due to
      the fact that we don't want to run
      any code after our nested loops, so
      the upcoming outer loop over all
      divisors will *start* with ';' to
      discard F(d+1). But on the first
      iteration we haven't called the
      subroutine yet, so we need some 
      dummy value we can discard.
dt&w  Run this loop once for each element     [d_1 d_2 ... d_p 1]
      in the stack. Note that this is once    OR
      more than we have divisors. But since   [d_i d_(i+1) ... F(d_(i-1)) F(d_(i-1)+1)] 
      we're treating the stack as a queue,
      the last iteration will process the 
      first divisor for a second time. 
      Luckily, the first divisor is always 
      1 and F(1) = 1, so it doesn't matter 
      how often we process this one.

  ;     Discard the dummy value on the        [d_1 d_2 ... d_p]
        first iteration and F(d+1) of         OR
        the previous divisor on subsequent    [d_i d_(i+1) ... F(d_(i-1))]
        iterations.
  31J   Call the subroutine without pushing   [d_(i+1) ... F(d_i) F(d_i+1)]
        the current address on the RAS.
        Thereby, this doubles as our outer
        loop end. As long as there's an
        address left from the 'w', the end
        of the subroutine will jump there
        and start another iteration for the
        next divisor. Once that's done, the
        'k' at the end of the subroutine will
        simply do nothing and we'll continue
        after it.

;     Discard the final F(d_i+1).
d&+   Get the stack depth D and add the top   [final result]
      D+2 values. Of course that's two more
      than we have divisors, but the stack is
      implicitly padded with zeros, so that
      doesn't matter.
\$\endgroup\$
1
\$\begingroup\$

Axiom, 68 bytes

g==>fibonacci;f(x:NNI):NNI==(x<3=>1;reduce(+,map(g,divisors(g(x)))))

some test

(46) -> [[i,f(i)] for i in [0,1,2,3,4,5,6,10,15] ]
   (46)
   [[0,1], [1,1], [2,1], [3,2], [4,3], [5,6], [6,26], [10,139583862540],
     [15,
      135823697912782666169062844948067355657769395021071830756126284114988028_
       12823029319917411196081011510136735503204397274473084444
     ]
   ]
                                       Type: List List NonNegativeInteger
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 34 bytes

n->sumdiv((f=fibonacci)(n),x,f(x))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 2, 89 84 bytes

-5 bytes thanks to ovs

lambda n:sum(f(i)for i in range(1,f(n)+1)if f(n)%i<1)
f=lambda x:x<3or f(x-1)+f(x-2)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

R, 77 bytes

F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)

Makes use of the 'gmp' library. This has a builtin Fibonacci function and provides the ability to do large numbers. It caused a few issues with seqs and applys, though it is still smaller than creating my own Fibonacci function.

Explanation

F=gmp::fibnum;               # Set F as fibnum function
N=F(scan());                 # get input and set N to the fibonacci number of that index
i=n=N-N;                     # set i and n to 0 with data type bigz
while(i<N)                   # loop while i < N
   if(N%%(i=i+1)<1)          # if incremented i is divisor of N 
       n=n+F(i);             # add F(i) to rolling sum
print(n)                     # output final result

Test

> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 6
2: 
Read 1 item
Big Integer ('bigz') :
[1] 26
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 10
2: 
Read 1 item
Big Integer ('bigz') :
[1] 139583862540
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 15
2: 
Read 1 item
Big Integer ('bigz') :
[1] 13582369791278266616906284494806735565776939502107183075612628411498802812823029319917411196081011510136735503204397274473084444

Without using gmp

81 bytes, Recursive function that is hopelessly slow when large (9+) numbers are picked

F=function(n)`if`(n<2,n,F(n-1)+F(n-2));sum(sapply(which((N=F(scan()))%%1:N<1),F))

88 bytes, Binet's formula that will work reasonably well with larger numbers, but still hits integer limit quite quickly

F=function(n)round(((5+5^.5)/10)*((1+5^.5)/2)^(n-1));sum(F(which(F(N<-scan())%%1:N<1)))
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 49 bytes

{my \f=0,1,*+*...*;sum f[grep f[$_]%%*,1..f[$_]]}
\$\endgroup\$
0
\$\begingroup\$

CJam, 26 bytes

qi_[XY@{_2$+}*]_@\f%:!.*:+

Try it online!

I'm sure it can be done better. Explanation:

The idea is to have an array of Fibonacci numbers and dot product it with an array with 1s and 0s if that number is or is not a divisor of the input.

qi                                 Read the input (n)
   [XY        ]                    Array starting with [1,2,...]
  _   @{_2$+}*                     Append n times the sum of the previous two
               _                   Duplicate the array
                @\f%               Modulo each item with n (0 if divisor, a number otherwise)
                    :!             Logical NOT everything (1 if divisor, 0 otherwise) 
                      .*:+         Dot product those two arrays
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 76 65 bytes

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

Test cases

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(4))
console.log(f(5))
console.log(f(6))

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 105 104 103 101 97 bytes

i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s

Try it

f=
i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s
o.innerText=f(j.value=4)
oninput=_=>o.innerText=f(+j.value)
<input id=j type=number><pre id=o>

\$\endgroup\$
  • \$\begingroup\$ I think you can change (z=g(i)/y)>~~z to (z=g(i)/y)%1, if you're just checking that z is an integer. \$\endgroup\$ – ETHproductions May 23 '17 at 16:20
  • \$\begingroup\$ @ETHproductions, that creates an overflow that can be solved by changing g(z) to g(z|0) but brings us back up to the same byte count. \$\endgroup\$ – Shaggy May 23 '17 at 16:35
0
\$\begingroup\$

Q, 75 bytes

{f:{$[x<2;x;.z.s[x-1]+.z.s[x-2]]};sum f each m where(~)b mod m:1+til b:f x}
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 93 90 80 bytes

F(n){n=n<2?n:F(n-1)+F(n-2);}i,s;f(n){for(s=0,i=F(n);i;i--)s+=F(n)%i?0:F(i);n=s;}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Add++, 89 bytes

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,r,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{r}
D,d,@,{g}dF€gs

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.