23
\$\begingroup\$

Divinacci (OEIS)

Perform the Fibonacci sequence but instead of using:

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

Use:

f(n) = sum(divisors(f(n-1))) + sum(divisors(f(n-2)))

For an input of n, output the nth term, your program should only have 1 input.


First 14 terms (0-indexed, you may 1-index; state which you used):

0  | 0     # Initial               | []
1  | 1     # Initial               | [1] => 1
2  | 1     # [] + [1]              | [1] => 1
3  | 2     # [1] + [1]             | [1,2] => 3
4  | 4     # [1] + [1,2]           | [1,2,4] => 7
5  | 10    # [1,2] + [1,2,4]       | [1,2,5,10] => 18
6  | 25    # [1,2,4] + [1,2,5,10]  | [1,5,25] => 31
7  | 49    # [1,2,5,10] + [1,5,25] | [1,7,49] => 57
8  | 88    # [1,5,25] + [1,7,49]   | [1, 2, 4, 8, 11, 22, 44, 88] => 180
9  | 237   # [1,7,49] + [180]      | [1, 3, 79, 237] => 320
10 | 500   # [180] + [320]         | [1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500] => 1092
11 | 1412  # [320] + [1092]        | [1, 2, 4, 353, 706, 1412] => 2478
12 | 3570  # [1092] + [2478]       | [1, 2, 3, 5, 6, 7, 10, 14, 15, 17, 21, 30, 34, 35, 42, 51, 70, 85, 102, 105, 119, 170, 210, 238, 255, 357, 510, 595, 714, 1190, 1785, 3570] => 10368
13 | 12846 # [2478] + [10368]      | [1, 2, 3, 6, 2141, 4282, 6423, 12846] => 25704
Etc...

You may choose whether or not to include the leading 0. For those who do: the divisors of 0 are [] for the purpose of this challenge.

It's lowest byte-count wins...

\$\endgroup\$
  • 15
    \$\begingroup\$ All natural numbers divide 0, thus its divisor sum is +∞. \$\endgroup\$ – Dennis Jun 23 '17 at 14:42
  • 9
    \$\begingroup\$ @Dennis finally someone who doesn't think that 1 + 2 + 3 + ... = -1/12. \$\endgroup\$ – Leaky Nun Jun 23 '17 at 14:54
  • 1
    \$\begingroup\$ @Dennis We can get rid of the 0 and make this valid though :P. Or you can just submit a Mathematica answer of Infinity if you want. \$\endgroup\$ – Magic Octopus Urn Jun 23 '17 at 15:05
  • \$\begingroup\$ The Jelly answer would be shorter. :P You can either change the sequence (the answer probably would need tweaking as well) or change its description (start with base values 0, 1, 1). \$\endgroup\$ – Dennis Jun 23 '17 at 15:19
  • 1
    \$\begingroup\$ @carusocomputing If it doesn't change the sequence, how can it affect answers? \$\endgroup\$ – Martin Ender Jun 23 '17 at 17:36

12 Answers 12

10
\$\begingroup\$

05AB1E, 9 bytes

XÎFDŠ‚ÑOO

Try it online!

Explanation

XÎ          # initialize stack with 1,0,input
  F         # input times do
   D        # duplicate
    Š       # move down 2 places on the stack
     ‚      # pair the top 2 elements on the stack
      Ñ     # compute divisors of each
       OO   # sum twice
\$\endgroup\$
  • \$\begingroup\$ Tons of swapping going on heh! Interesting. \$\endgroup\$ – Magic Octopus Urn Jun 23 '17 at 14:07
  • 2
    \$\begingroup\$ I like how the last couple bytes are forcefully yelling at the reader. \$\endgroup\$ – Rohan Jhunjhunwala Jun 24 '17 at 18:07
  • 1
    \$\begingroup\$ You won this by 2 minutes lol. \$\endgroup\$ – Magic Octopus Urn Aug 17 '17 at 21:47
8
\$\begingroup\$

Mathematica, 45 40 bytes

If[#<3,1,Tr@Divisors@#0[#-i]~Sum~{i,2}]&

Mathematica's divisor related functions Divisors, DivisorSum and DivisorSigma are all undefined for n = 0 (rightly so), so we start from f(1) = f(2) = 1 and don't support input 0.

Defining it as an operator instead of using an unnamed function seems to be two bytes longer:

±1=±2=1
±n_:=Sum[Tr@Divisors@±(n-i),{i,2}]
\$\endgroup\$
  • \$\begingroup\$ *7 bytes longer unless ± is 1 byte in a Mathematica supported encoding. \$\endgroup\$ – CalculatorFeline Jun 23 '17 at 16:31
  • \$\begingroup\$ @CalculatorFeline It is. (The default setting for $CharacterEncoding on Windows machines is WindowsANSI, i.e. CP 1252.) \$\endgroup\$ – Martin Ender Jun 23 '17 at 17:29
  • 1
    \$\begingroup\$ Good to know. . \$\endgroup\$ – CalculatorFeline Jun 23 '17 at 18:48
5
\$\begingroup\$

Perl 6, 58 bytes

{my&d={sum grep $_%%*,1..$_};(0,1,{d($^a)+d $^b}...*)[$_]}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Haskell, 55 bytes

f n=sum[a|n>1,k<-f<$>[n-1,n-2],a<-[1..k],mod k a<1]+0^n

Try it online!

One-indexed.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 76 bytes

f=lambda n:sum(a for k in[1,2][:n]for a in range(1,3**n-8)if f(n-k)%a<1)or n

Try it online!

Ridiculously slow.

\$\endgroup\$
3
\$\begingroup\$

MATL, 16 15 bytes

Oliq:",yZ\s]+]&

This solution uses 0-based indexing.

Try it at MATL Online

Explanation

O        % Push the number literal 0 to the stack
l        % Push the number literal 1 to the stack
i        % Explicitly grab the input (n)
q        % Subtract 1
:        % Create the array [1...(n - 1)]
"        % For each element in this array...
  ,      % Do the following twice
    y    % Copy the stack element that is 1-deep
    Z\   % Compute the divisors
    s    % Sum the divisors
  ]      % End of do-twice loop
  +      % Add these two numbers together
]        % End of for loop
&        % Display the top stack element
\$\endgroup\$
3
\$\begingroup\$

Jelly, 10 9 bytes

ð,ÆDẎSð¡1

Try it online!

Thanks to Dennis for -1.

\$\endgroup\$
  • \$\begingroup\$ 9 bytes \$\endgroup\$ – Dennis Jun 23 '17 at 15:49
  • \$\begingroup\$ @Dennis The 0 was implicit? \$\endgroup\$ – Erik the Outgolfer Jun 23 '17 at 15:52
  • \$\begingroup\$ When you take the number of iterations from STDIN, you get a niladic chain, and 0 is the implicit argument of niladic chains. \$\endgroup\$ – Dennis Jun 23 '17 at 15:53
  • \$\begingroup\$ @Dennis So ¡ and others will just try to take an argument from everywhere, even with a Ɠ? That's quite unexpected... \$\endgroup\$ – Erik the Outgolfer Jun 23 '17 at 15:54
  • \$\begingroup\$ Unless specified explicitly, ¡ et al. take the last command-line argument and, if there aren't any, reads a line from STDIN. \$\endgroup\$ – Dennis Jun 23 '17 at 15:56
3
\$\begingroup\$

Python 3, 88 83 81 bytes

f=lambda n:+(n<3)or g(f(n-1))+g(f(n-2))
g=lambda n,i=1:n>=i and(n%i<1)*i+g(n,i+1)

Try it online!

Excludes the 0

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

Haskell, 64 60 bytes

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

Try it online!

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

PHP, 97 bytes

for($f=[0,$y=1];++$i<$argn;$x=$y,$y=$r)for($f[]=$r=$v=$n=$x+$y;--$v;)$n%$v?:$r+=$v;echo$f[$argn];

Try it online!

PHP, 101 bytes

for($f=$d=[0,1];$i<$argn;$d[]=$r)for($f[]=$r=$v=$n=$d[$i]+$d[++$i];--$v;)$n%$v?:$r+=$v;echo$f[$argn];

Try it online!

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

Pari/GP, 39 bytes

f(n)=if(n<3,1,sum(i=1,2,sigma(f(n-i))))

Based on Martin Ender's Mathematica answer.

Try it online!

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

R, 81 bytes

f=function(n,a=1,b=1,d=numbers::divisors)`if`(n-1,f(n-1,b,sum(d(a))+sum(d(b))),a)

1-indexed, and excludes the 0 at the start of the sequence. That zero gave me a lot of trouble to implement, because the builtin numbers::divisors doesnt handle it well.

The rest is a modified version of the standard recursive function that implements the fibonacci sequence.

> f(1)
[1] 1
> f(2)
[1] 1
> f(3)
[1] 2
> f(5)
[1] 10
> f(13)
[1] 12846
\$\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.