25
\$\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\$
13
  • 15
    \$\begingroup\$ All natural numbers divide 0, thus its divisor sum is +∞. \$\endgroup\$
    – Dennis
    Jun 23, 2017 at 14:42
  • 9
    \$\begingroup\$ @Dennis finally someone who doesn't think that 1 + 2 + 3 + ... = -1/12. \$\endgroup\$
    – Leaky Nun
    Jun 23, 2017 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\$ Jun 23, 2017 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, 2017 at 15:19
  • 1
    \$\begingroup\$ @carusocomputing If it doesn't change the sequence, how can it affect answers? \$\endgroup\$ Jun 23, 2017 at 17:36

19 Answers 19

12
\$\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\$
3
  • \$\begingroup\$ Tons of swapping going on heh! Interesting. \$\endgroup\$ Jun 23, 2017 at 14:07
  • 2
    \$\begingroup\$ I like how the last couple bytes are forcefully yelling at the reader. \$\endgroup\$ Jun 24, 2017 at 18:07
  • 1
    \$\begingroup\$ You won this by 2 minutes lol. \$\endgroup\$ Aug 17, 2017 at 21:47
9
\$\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\$
3
  • \$\begingroup\$ *7 bytes longer unless ± is 1 byte in a Mathematica supported encoding. \$\endgroup\$ Jun 23, 2017 at 16:31
  • \$\begingroup\$ @CalculatorFeline It is. (The default setting for $CharacterEncoding on Windows machines is WindowsANSI, i.e. CP 1252.) \$\endgroup\$ Jun 23, 2017 at 17:29
  • 1
    \$\begingroup\$ Good to know. . \$\endgroup\$ Jun 23, 2017 at 18:48
6
\$\begingroup\$

Perl 6, 58 bytes

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

Try it online!

\$\endgroup\$
5
\$\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\$
4
\$\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\$
4
\$\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\$
4
\$\begingroup\$

Jelly, 10 9 bytes

ð,ÆDẎSð¡1

Try it online!

Thanks to Dennis for -1.

\$\endgroup\$
5
  • \$\begingroup\$ 9 bytes \$\endgroup\$
    – Dennis
    Jun 23, 2017 at 15:49
  • \$\begingroup\$ @Dennis The 0 was implicit? \$\endgroup\$ Jun 23, 2017 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, 2017 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\$ Jun 23, 2017 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, 2017 at 15:56
4
\$\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\$
3
\$\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\$
3
\$\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\$
3
\$\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\$
2
\$\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\$
2
\$\begingroup\$

Vyxal, 9 bytes

1{~"vKf∑…

Try it Online!

Prints the sequence forever.

1         # Push 1
 {        # Forever...
  ~"      # Grab top two elements, without popping
    vK    # Get divisors of each
      f∑  # Deep sum
        … # Print that without popping
\$\endgroup\$
2
\$\begingroup\$

Julia, 47 44 bytes

~n=(n.%(r=1:n).<1)'r
!N=N<3||~!(N-1)+~!(N-2)

Attempt This Online!

-3 bytes thanks to Czylabson Asa. (I forgot how a'*b worked)

\$\endgroup\$
5
  • \$\begingroup\$ gives true for N=1,2 \$\endgroup\$ Jun 13 at 20:31
  • \$\begingroup\$ @CzylabsonAsa true == 1, so I think it's ok \$\endgroup\$
    – MarcMush
    Jun 13 at 21:02
  • 1
    \$\begingroup\$ oh, really. just a short note, your ~ can be ~m=(r=1:m;r'*(m.%r.<1)), not shorter, but a little bit different. \$\endgroup\$ Jun 13 at 21:11
  • \$\begingroup\$ thanks, I knew I could do better but I forgot about how finicky a'*b was to get a number instead of a 1x1 matrix \$\endgroup\$
    – MarcMush
    Jun 13 at 21:26
  • 1
    \$\begingroup\$ w/similar method i got 6th (20220615) at code.golf/abundant-numbers :-) \$\endgroup\$ Jun 14 at 19:53
1
\$\begingroup\$

Husk, 11 bytes

!¡ȯΣṁḊ↑_2ŀ2

Try it online!

Explanation

!¡ȯΣṁḊ↑_2ŀ2
         ŀ2 array [0,1]
 ¡          iterate on the array, expanding it:
  ȯ         using the following 4 functions:
      ↑_2   get last 2 elements
    ṁḊ      get divisors of both
   Σ        sum them
!           Get element at index n
\$\endgroup\$
1
\$\begingroup\$

Factor + math.primes.factors math.unicode, 53 bytes

[ 0 1 rot [ tuck [ divisors Σ ] bi@ + ] times drop ]

Try it online!

0-indexed.

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

C (gcc), 93 87 86 bytes

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

Try it online!

A simple recursive solution that finds divisors by brute force.

Thanks to @ceilingcat for -6 bytes on the for loop and -1 on some superfluous parens.

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

Burlesque, 23 bytes

0 1 2{fc++jfc++.+}C~j!!

Try it online!

0 1   # Initial 
2     # Keep top 2 stack elements
{
 fc++ # Factors, Sum
 j    # Swap stack
 fc++ # Factors, Sum
 .+   # Sum
}C~   # Continue forever
j!!   # Get input element
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 7 bytes

1λè‚јO

Outputs the 1-based \$n^{th}\$ value.

Try it online.

With some small modifications, we could output:

  • 7 bytes: The first 1-based \$n\$ values by replacing è with £: try it online.
  • 5 bytes: The infinite 1-based sequence by removing the 1 and è: try it online.
  • Or with 0-based sequence by adding Ý after the 1:

So with default sequence rules, this could have been 5 bytes.

Explanation:

 λ       # Start a recursive environment,
  è      # to output the a(input)'th value
         # (which is output implicitly at the end)
1        # Starting at a(0)=1
         # And where every following a(n) is calculated as:
   ‚     #  Pair the (implicit) previous two terms together: [a(n-2),a(n-1)]
         #  (a(n-2) is unknown in the first iteration, so will default to 0)
    Ñ    #  Get the divisors of both inner values
     ˜   #  Flatten this list of lists of integers
      O  #  Sum them together

Explanation of the 5-bytes infinite 1-based sequence:

λ        # Start a recursive environment,
         # to output the infinite sequence
         # (which is output implicitly at the end)
         # Implicitly starting at a(0)=1
         # And where every following a(n) is calculated as:
 ‚јO    #  See above
\$\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.