20
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice first challenge, btw. :) \$\endgroup\$ – Martin Ender Jul 12 '16 at 7:06
  • 1
    \$\begingroup\$ if the language cant manage 10k chars strings?? (e.g. the awful Oracle SQL 4k limit)is the answer valid if it's the language limit? \$\endgroup\$ – Giacomo Garabello Jul 12 '16 at 9:57
  • \$\begingroup\$ @MartinEnder, thanks! And thanks for that link; it was enlightening. Is there anything out there that explains how to treat answers in languages with limitations? I couldn't find anything, but I know that doesn't mean it's not there. :) \$\endgroup\$ – Joe Jul 12 '16 at 23:49
  • \$\begingroup\$ I may be being completely thick, but how are the numbers in that series calculated? \$\endgroup\$ – Tom Carpenter Jul 13 '16 at 2:28
  • \$\begingroup\$ @TomCarpenter: For the first element, take all the divisors of 1 that are less than 1, and add them together. (1 is the only divisor of 1, so the first element ends up being zero.) Second element, the divisors of 2 that are less than 2 (only 1 fits this); third, divisors of 3 (still just 1); and so on. The divisors of 4 are {1, 2}, and 1+2==3, so the fourth element is 3. It took me a while to figure it out too ;) \$\endgroup\$ – Joe Jul 13 '16 at 17:46

12 Answers 12

6
\$\begingroup\$

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!.

\$\endgroup\$
6
\$\begingroup\$

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.

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

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
    
\$\endgroup\$
  • 1
    \$\begingroup\$ You can allocate more global stack with the -G option. The default is only 128M. You can use for example: swipl -G2G to use 2 GO. \$\endgroup\$ – mat Jul 12 '16 at 9:10
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What's up with that complicated divisor search? f!%dTr1d is much shorter (but also slower) \$\endgroup\$ – Jakube Jul 12 '16 at 9:24
  • \$\begingroup\$ @Jakube whoops, modified the wrong version for the 20 byte solution. \$\endgroup\$ – PurkkaKoodari Jul 12 '16 at 9:27
  • \$\begingroup\$ f!%TYtUT is what I used to have. \$\endgroup\$ – PurkkaKoodari Jul 12 '16 at 9:29
  • \$\begingroup\$ @Jakube I changed to that. It's still running for n = 9999, been over 5 mins now :\ \$\endgroup\$ – PurkkaKoodari Jul 12 '16 at 10:02
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ ÆDṖSDµ€Fị@ saves a byte. \$\endgroup\$ – Dennis Jul 12 '16 at 14:26
  • \$\begingroup\$ @Dennis so does that apply the to the entire first chain? \$\endgroup\$ – PurkkaKoodari Jul 13 '16 at 5:55
  • \$\begingroup\$ @Pietu1998: Yes, precisely: in general, at parse time, is applied to chain.pop() if chain else chains.pop(). The newly started chain is empty, so the last finished chain is used instead. \$\endgroup\$ – Lynn Jul 13 '16 at 12:59
3
\$\begingroup\$

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.

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

J, 34 bytes

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

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

Formula

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

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

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.

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

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.

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

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.

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

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);
}
\$\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.