Divinacci Sequence

Question

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 code-golf lowest byte-count wins...

@Dennis finally someone who doesn't think that 1 + 2 + 3 + ... = -1/12. — Leaky Nun, Jun 23, 2017 at 14:54
@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. — Magic Octopus Urn, Jun 23, 2017 at 15:05
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). — Dennis, Jun 23, 2017 at 15:19
@carusocomputing If it doesn't change the sequence, how can it affect answers? — Martin Ender, Jun 23, 2017 at 17:36

Emigna · Accepted Answer · 2017-06-23 14:02:07Z

12

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

answered Jun 23, 2017 at 14:02

Emigna

52.8k5 gold badges41 silver badges161 bronze badges

\$\begingroup\$ Tons of swapping going on heh! Interesting. \$\endgroup\$
– Magic Octopus Urn
Jun 23, 2017 at 14:07
2

\$\begingroup\$ I like how the last couple bytes are forcefully yelling at the reader. \$\endgroup\$
– Rohan Jhunjhunwala
Jun 24, 2017 at 18:07
1

\$\begingroup\$ You won this by 2 minutes lol. \$\endgroup\$
– Magic Octopus Urn
Aug 17, 2017 at 21:47

Add a comment |

Martin Ender · Accepted Answer · 2017-06-23 19:32:26Z

9

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}]

edited Jun 23, 2017 at 19:32

answered Jun 23, 2017 at 14:35

Martin Ender

195k65 gold badges441 silver badges962 bronze badges

\$\begingroup\$ *7 bytes longer unless ± is 1 byte in a Mathematica supported encoding. \$\endgroup\$
– CalculatorFeline
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\$
– Martin Ender
Jun 23, 2017 at 17:29
1

\$\begingroup\$ Good to know. . \$\endgroup\$
– CalculatorFeline
Jun 23, 2017 at 18:48

Add a comment |

Sean · Accepted Answer · 2017-06-23 17:34:59Z

6

Perl 6, 58 bytes

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

Try it online!

answered Jun 23, 2017 at 17:34

Sean

7,1869 silver badges15 bronze badges

Add a comment |

xnor · Accepted Answer · 2017-06-23 17:41:27Z

5

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.

answered Jun 23, 2017 at 17:41

xnor

141k26 gold badges268 silver badges618 bronze badges

Add a comment |

xnor · Accepted Answer · 2017-06-23 18:11:27Z

4

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.

answered Jun 23, 2017 at 18:11

xnor

141k26 gold badges268 silver badges618 bronze badges

Add a comment |

Erik the Outgolfer · Accepted Answer · 2017-06-24 13:54:52Z

4

Jelly, 10 9 bytes

ð,ÆDẎSð¡1

Try it online!

Thanks to Dennis for -1.

edited Jun 24, 2017 at 13:54

answered Jun 23, 2017 at 14:04

Erik the Outgolfer

40.3k5 gold badges39 silver badges120 bronze badges

\$\begingroup\$ 9 bytes \$\endgroup\$
– Dennis
Jun 23, 2017 at 15:49
\$\begingroup\$ @Dennis The 0 was implicit? \$\endgroup\$
– Erik the Outgolfer
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\$
– Erik the Outgolfer
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

Add a comment |

ovs · Accepted Answer · 2017-06-25 10:47:25Z

4

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

edited Jun 25, 2017 at 10:47

answered Jun 23, 2017 at 15:12

ovs

56.1k3 gold badges41 silver badges150 bronze badges

Add a comment |

Suever · Accepted Answer · 2022-09-04 02:14:34Z

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

vroomfondel · Accepted Answer · 2017-06-23 14:55:54Z

3

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!

edited Jun 23, 2017 at 14:55

answered Jun 23, 2017 at 14:18

vroomfondel

2,2541 gold badge10 silver badges23 bronze badges

Add a comment |

Jörg Hülsermann · Accepted Answer · 2017-06-23 15:53:15Z

3

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!

edited Jun 23, 2017 at 15:53

answered Jun 23, 2017 at 15:21

Jörg Hülsermann

13.3k3 gold badges13 silver badges36 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2017-06-25 03:07:48Z

3

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!

answered Jun 25, 2017 at 3:07

alephalpha

41.7k6 gold badges52 silver badges151 bronze badges

Add a comment |

JAD · Accepted Answer · 2017-06-23 20:04:22Z

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

emanresu A · Accepted Answer · 2022-06-13 01:52:49Z

2

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

answered Jun 13, 2022 at 1:52

emanresu A

34k5 gold badges77 silver badges185 bronze badges

Add a comment |

MarcMush · Accepted Answer · 2022-06-14 10:33:20Z

2

Julia, ⁴⁷ 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)

edited Jun 14, 2022 at 10:33

answered Jun 13, 2022 at 16:18

MarcMush

5,7049 silver badges15 bronze badges

\$\begingroup\$ gives true for N=1,2 \$\endgroup\$
– Czylabson Asa
Jun 13, 2022 at 20:31
\$\begingroup\$ @CzylabsonAsa true == 1, so I think it's ok \$\endgroup\$
– MarcMush
Jun 13, 2022 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\$
– Czylabson Asa
Jun 13, 2022 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, 2022 at 21:26
1

\$\begingroup\$ w/similar method i got 6th (20220615) at code.golf/abundant-numbers :-) \$\endgroup\$
– Czylabson Asa
Jun 14, 2022 at 19:53

Add a comment |

Razetime · Accepted Answer · 2020-10-09 08:37:22Z

1

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

answered Oct 9, 2020 at 8:37

Razetime

26.4k3 gold badges25 silver badges71 bronze badges

Add a comment |

chunes · Accepted Answer · 2022-06-13 01:38:34Z

1

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

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

Try it online!

0-indexed.

answered Jun 13, 2022 at 1:38

chunes

16.6k3 gold badges15 silver badges42 bronze badges

Add a comment |

evanstar3 · Accepted Answer · 2022-06-13 18:55:27Z

1

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.

edited Jun 13, 2022 at 18:55

answered Jun 13, 2022 at 13:14

evanstar3

1514 bronze badges

Add a comment |

DeathIncarnate · Accepted Answer · 2022-06-13 21:55:51Z

1

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

answered Jun 13, 2022 at 21:55

DeathIncarnate

2,4806 silver badges9 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-06-14 11:43:47Z

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:
- 8 bytes: 0-based \$n^{th}\$: try it online.
- 8 bytes: 0-based first \$n\$ values: try it online.
- 7 bytes: 0-based infinite sequence: try it online.

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

Stack Exchange Network

Divinacci Sequence

Divinacci (OEIS)

19 Answers 19

05AB1E, 9 bytes

Mathematica, 45 40 bytes

Perl 6, 58 bytes

Haskell, 55 bytes

Python 2, 76 bytes

Jelly, 10 9 bytes

Python 3, 88 83 81 bytes

MATL, 16 15 bytes

Haskell, 64 60 bytes

PHP, 97 bytes

PHP, 101 bytes

Pari/GP, 39 bytes

R, 81 bytes

Vyxal, 9 bytes

Julia, ⁴⁷ 44 bytes

Husk, 11 bytes

Explanation

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

C (gcc), 93 87 86 bytes

Burlesque, 23 bytes

05AB1E, 7 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
number-theory
fibonacci
division
or ask your own question.

Hot Network Questions

Divinacci Sequence

Divinacci (OEIS)

19 Answers 19

05AB1E, 9 bytes

Mathematica, 45 40 bytes

Perl 6, 58 bytes

Haskell, 55 bytes

Python 2, 76 bytes

Jelly, 10 9 bytes

Python 3, 88 83 81 bytes

MATL, 16 15 bytes

Haskell, 64 60 bytes

PHP, 97 bytes

PHP, 101 bytes

Pari/GP, 39 bytes

R, 81 bytes

Vyxal, 9 bytes

Julia, 47 44 bytes

Husk, 11 bytes

Explanation

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

C (gcc), 93 87 86 bytes

Burlesque, 23 bytes

05AB1E, 7 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Julia, ⁴⁷ 44 bytes

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

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
number-theory
fibonacci
division
or ask your own question.