Return the nth digit of the sequence of aliquot series

Question

0. DEFINITIONS

A sequence is a list of numbers.
A series is the sum of a list of numbers.
The set of natural numbers contains all "non-negative integers greater than zero".
A divisor (in this context) of a natural number j is a natural number i, such that j÷i is also a natural number.

1. PREAMBLE

A couple of other questions on this site mention the concept of the aliquot, or the sequence of divisors of a natural number a which are less than a. Determining amicable numbers involves computing the sum of these divisors, called an aliquot sum or aliquot series. Every natural number has its own aliquot sum, although the value of a number's aliquot sum is not necessarily unique to that number. (Exempli gratia, every prime number has an aliquot sum of 1.)

2. CHALLENGE

Given a natural number n, return the nth digit of the sequence of aliquot sums. The first several series in the sequence, starting with the series for 1, are:

{0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13}

Concatenated, these look like:

0113161748116110915121122111413661613

Input may be zero-indexed or one-indexed, according to your preference. Solutions must be programs or functions capable of returning the 10,000th digit (input up to 9999 or 10000). The shortest working solution wins.

3. TEST CASES

Correct input-output pairs should include, but are not limited to, the following:

   0 or     1    ->    0
   4 or     5    ->    1
  12 or    13    ->    6
9999 or 10000    ->    7

The number preceding the "or" is 0-indexed; the number following is 1-indexed.
Additional test cases may be provided upon request.

4. REFERENCES

OEIS has a list of numbers and their aliquot sums.

Answer 1

05AB1E, 14 11 10 bytes

Compute n = 9999 in about 15 seconds. Code:

ÌL€Ñ€¨OJ¹è

Explanation:

Ì           # Increment implicit input by 2
 L          # Generate the list [1 .. input + 2]
  ۄ        # For each, get the divisors
    ۬      # For each, pop the last one out
      O     # Sum all the arrays in the array
       J    # Join them all together
        ¹è  # Get the nth element

Uses the CP-1252 encoding. Try it online!.

Answer 2

Mathematica, 51 bytes

Array[##&@@IntegerDigits[Tr@Divisors@#-#]&,#][[#]]&

An unnamed function which takes and returns an integer and uses 1-based indexing. Handles input 10000 instantly.

Explanation

This is a very straight-forward implementation of the definition, making use of the fact that the first n divisor sums are always enough to determine the nth digit. As usual, the reading order of golfed Mathematica is a bit funny though:

Array[...&,#]...&

This generates a list with all the results of applying the unnamed function on the left to all the values i from 1 to n inclusive.

...Tr@Divisors@#-#...

We start by computing the divisors of i, summing them with Tr and subtracting i itself so that it's just the sum of divisors less than i.

...IntegerDigits[...]...

This turns the result into a list of its decimal digits.

##&@@...

And this removes the "list" head, so that all the digit lists are automatically concatenated in the result of Array. For more details on how ## works, see the "Sequences of arguments" section in this post.

...[[#]]

Finally, we select the nth digit from the result.

Answer 3

Brachylog, 40 bytes

:2-I,?:?:1yrc:Im.;0.
:1e:2f+.
>.>0,?:.%0

This is 1-indexed, takes about 0.15 seconds for N = 100, 15 seconds for N = 1000. I'm currently running for N = 10000, I'll report the run time once it ends (If my estimation is correct, it should take about 8 hours)

Edit: by fixing premature constraints propagation in Brachylog, it now (on a 3 bytes longer code) takes about 2.5 minutes for 10000 but returns an out of global stack error.

Explanation

• Main Predicate: Input = N

  :2-I,                 I = N - 2
       ?:?:1y           Find the N first valid outputs of predicate 1 with input N
             rc         Reverse and concatenate into a single number
               :Im.     Output is the Ith digit of that number
                   ;    Or (I strictly less than 0)
                    0.  Output is 0
  

• Predicate 1: computes the sum of the divisors

  :1e                   Get a number between N and 1
     :2f                Find all valid outputs of predicate 2 with that number as input
        +.              Output is the sum of those outputs
  

• Predicate 2: unifies output with a divisor of the input

  >.>0,                 Output is a number between Input and 0
       ?:.%0            Input is divisible by Output
  

Answer 4

Pyth, 26 21 20 15 bytes

@sm`sf!%dTtUdSh

Try it online. Test suite.

Uses 0-based indexing. The program is O(n²) and completes for n = 9999 in about 14 minutes on my 2008 machine.

Answer 5

Jelly, 13 11 10 bytes

2 bytes thanks to @Adnan and 1 more thanks to @Dennis.

ÆDṖSDµ€Fị@

Try it online!

Uses 1-based indexing. Completes for n = 10000 in under 2 seconds online.

Answer 6

PHP, 90 bytes

0 indexed

<?php for(;strlen($s)<=$a=$argv[1];$s.=$n)for($n=0,$j=++$i;--$j;)$i%$j||$n+=$j;echo$s[$a];

Absolutely not subtle or with a clever way of approaching it at all.
Also, as usual, produces three notices which are ignored.

Answer 7

J, 34 bytes

{[:;1<@":@(-~>:@#.~/.~&.q:)@+i.@>:

This is zero-indexed and uses the formula below to calculate the divisor sums.

Explanation

{[:;1<@":@(-~>:@#.~/.~&.q:)@+i.@>:  Input: n
                                >:  Increment n
                             i.@    Create the range [0, 1, ..., n]
    1                       +       Add one to each to get [1, 2, ..., n+1]
          (               )@        For each value
                        q:            Get the prime factors
                   /.~&.              For each group of equal prime factors
                #.~                     Raise the first to the first power, the second
                                        squared and so on, and sum them
             >:@                        Increment that sum
                      &.q:            Reduce the groups using multiplication
           -~                         Subtract the initial value from that sum
       ":@                            Convert each to a string
     <@                               Box each
 [:;                                Unbox each and concatenate the strings
{                                   Select the character from that string at index n
                                    and return it

Answer 8

MATL, 16 15 bytes

:"@@q:\~fsV]vG)

Indexing is 1-based.

The last test case times out in the online compiler, but it does give the correct result with the offline compiler, in about 15 seconds.

Try it online!

:         % Take input n. Push [1 2 ... n]
"         % For each k in [1 2 ... n]
  @       %   Push k
  @q:     %   Push [1 2 ... k-1]
  \       %   Modulo. Zero values correspond to divisors
  ~f      %   Indices of zeros. These are the divisors
  s       %   Sum
  V       %   Convert to string
]         % End for each
v         % Concatenate all stack contents vertically
G)        % Take n-th digit. Implicitly display

Answer 9

Haskell, 52 bytes

(([1..]>>= \n->show$sum[m|m<-[1..n-1],mod n m<1])!!)

Usage example: (([1..]>>= \n->show$sum[m|m<-[1..n-1],mod n m<1])!!) 12-> 6.

It's a direct implementation of the definition: foreach n sum it's divisors and convert it into a string. Concatenate all such strings and pick the element at the requested index. Haskell's laziness takes only as much ns from the infinite list [1..] as needed.

Answer 10

Python 3.5, 103 93 92 bytes:

R=range;A=lambda f:''.join([str(sum([j for j in R(1,i)if i/j%1==0]))for i in R(1,f+1)])[f-1]

Pretty straightforward implementation of method described in post.

Try It Online! (Ideone)

Does not quite finish within the allotted 5 seconds in the online compiler for input 10000, but it does finish on my machine for the same input within about 8.5 seconds.

Answer 11

Husk, 8 bytes

!ṁödΣhḊN

Try it online!

Answer 12

Octave, 71 bytes

This one is Octave only. It won't work in MATLAB. A virtual function is created which works on 1-indexed numbers. It can probably be simplified a bit further. Will have a look this evening.

@(x)c((c=num2str(arrayfun(@(n)sum(b(~rem(n,b=(1:n-1)))),1:x)))~=' ')(x)

You can try online here.

Simply run the command above, prefixed with a= or whatever (just so that you can use it multiple times), and then do a(10000) or whatever. It takes about 7 seconds to calculated that the 10000th digit is a 7.

Answer 13

Java 8, 220 bytes

import java.util.stream.IntStream;
char a(int n){return IntStream.range(1,n+2).map(i->IntStream.range(1,i).filter(k->i%k==0).sum()).mapToObj(Integer::toString).collect(java.util.stream.Collectors.joining("")).charAt(n);}

Well, it's fast at least. It averages 0.3 seconds to get the 9999/10000th element on my machine. It generates only as many aliquot sums as the index you specified. This means the string will be slightly longer than your index in most cases, since some aliquot sums have 2 or more digits, but for the most part, it only generates as long of a string as we need.

Usage:

public static void main(String[] args) {
    System.out.println(a(0));
    System.out.println(a(4));
    System.out.println(a(12));
    System.out.println(a(9999));
}

Ungolfed:

public static void main(String[] args) {
    System.out.println(all(0));
    System.out.println(all(4));
    System.out.println(all(12));
    System.out.println(all(9999));
}

static int aliquotSum(int n) {
    return IntStream.range(1, n).filter(k -> n % k == 0).sum();
}

static IntStream sums(int n) {
    return IntStream.range(1, n + 2).map(i -> aliquotSum(i));
}

static String arraycat(IntStream a) {
    return a.mapToObj(Integer::toString).collect(java.util.stream.Collectors.joining(""));
}

static char all(int index) {
    return arraycat(sums(index)).charAt(index);
}