Code Golf Asked on December 21, 2020
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.
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.)
Given a natural number n
, return the n
th 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.
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.
OEIS has a list of numbers and their aliquot sums.
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!.
Correct answer by Adnan on December 21, 2020
Answered by Razetime on December 21, 2020
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);
}
Answered by Justin on December 21, 2020
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.
Answered by Tom Carpenter on December 21, 2020
(([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 n
s from the infinite list [1..]
as needed.
Answered by nimi on December 21, 2020
2 bytes thanks to @Adnan and 1 more thanks to @Dennis.
ÆDṖSDµ€Fị@
Uses 1-based indexing. Completes for n = 10000 in under 2 seconds online.
Answered by PurkkaKoodari on December 21, 2020
:"@@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.
: % 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
Answered by Luis Mendo on December 21, 2020
{[:;1<@":@(-~>:@#.~/.~&.q:)@+i.@>:
This is zero-indexed and uses the formula below to calculate the divisor sums.
{[:;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
Answered by miles on December 21, 2020
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.
Answered by user55641 on December 21, 2020
: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.
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
Answered by Fatalize on December 21, 2020
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.
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.
Answered by R. Kap on December 21, 2020
@sm`sf!%dTtUdSh
Uses 0-based indexing. The program is O(n²) and completes for n = 9999 in about 14 minutes on my 2008 machine.
Answered by PurkkaKoodari on December 21, 2020
Array[##&@@IntegerDigits[Tr@Divisors@#-#]&,#][[#]]&
An unnamed function which takes and returns an integer and uses 1-based indexing. Handles input 10000
instantly.
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 n
th 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 n
th digit from the result.
Answered by Martin Ender on December 21, 2020
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP