Gibt die n-te Ziffer der Folge von Aliquotserien zurück

20

0. BEGRIFFSBESTIMMUNGEN

Eine Sequenz ist eine Liste von Zahlen.
Eine Reihe ist die Summe einer Liste von Zahlen.
Die Menge der natürlichen Zahlen enthält alle "nicht negativen ganzen Zahlen größer als Null".
Ein Teiler (in diesem Zusammenhang) einer natürlichen Zahl j ist eine natürliche Zahl i , so dass j ÷ i auch eine natürliche Zahl ist.

1. PRÄAMBEL

Einige andere Fragen auf dieser Seite erwähnen das Konzept des Aliquots oder die Folge von Teilern einer natürlichen Zahl a, die kleiner als a sind . Das Bestimmen von gütlichen Zahlen umfasst das Berechnen der Summe dieser Teiler, die als Aliquotsumme oder Aliquotserie bezeichnet wird. Jede natürliche Zahl hat ihre eigene aliquote Summe, obwohl der Wert der aliquoten Summe einer Zahl nicht unbedingt für diese Zahl eindeutig ist. ( Exempli gratia , jede Primzahl hat eine aliquote Summe von 1.)

2. HERAUSFORDERUNG

Geben Sie bei einer natürlichen Zahl ndie ndritte Ziffer der Folge von Aliquotsummen zurück. Die ersten Serien in der Sequenz, beginnend mit der Serie für 1, sind:

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

Verkettet sehen diese so aus:

0113161748116110915121122111413661613

Die Eingabe kann je nach Wunsch null- oder einindexiert sein. Lösungen müssen Programme oder Funktionen sein, die die 10.000ste Ziffer zurückgeben können (Eingabe bis 9999oder 10000). Die kürzeste funktionierende Lösung gewinnt.

3. TESTFÄLLE

Die korrekten Eingabe-Ausgabe-Paare sollten Folgendes umfassen, sind jedoch nicht darauf beschränkt:

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

Die Zahl vor dem "oder" ist 0-indiziert. Die folgende Nummer ist 1-indiziert.
Weitere Testfälle können auf Anfrage zur Verfügung gestellt werden.

4. Referenzen

OEIS hat eine Liste von Zahlen und deren aliquoten Summen.

Joe
quelle
2
Schöne erste Herausforderung, übrigens. :)
Martin Ender
1
wenn die Sprache 10k Zeichenketten nicht handhaben kann ?? (zB das schreckliche Oracle SQL 4k-Limit ) Ist die Antwort gültig, wenn es das Sprachlimit ist?
Giacomo Garabello
@ MartinEnder, danke! Und danke für diesen Link; es war aufschlussreich. Gibt es irgendetwas, das erklärt, wie man Antworten in Sprachen mit Einschränkungen behandelt? Ich konnte nichts finden, aber ich weiß, das heißt nicht, dass es nicht da ist. :)
Joe
Ich bin vielleicht ganz dick, aber wie werden die Zahlen in dieser Reihe berechnet?
Tom Carpenter
@TomCarpenter: Nehmen Sie für das erste Element alle Teiler von 1, die kleiner als 1 sind, und addieren Sie sie. (1 ist der einzige Teiler von 1, so dass das erste Element null ist.) Zweites Element, die Teiler von 2, die kleiner als 2 sind (nur 1 passt dazu); drittens Teiler von 3 (immer noch nur 1); und so weiter. Die Teiler von 4 sind {1, 2} und 1 + 2 == 3, also ist das vierte Element 3. Es hat eine Weile
Joe

Antworten:

6

05AB1E , 14 11 10 Bytes

Berechnen Sie n = 9999 in ungefähr 15 Sekunden. Code:

ÌL€Ñ€¨OJ¹è

Erläuterung:

Ì           # 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

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
6

Mathematica, 51 Bytes

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

Eine unbenannte Funktion, die eine Ganzzahl annimmt und zurückgibt und eine 1-basierte Indizierung verwendet. Verarbeitet die Eingabe 10000sofort.

Erläuterung

Dies ist eine sehr einfache Implementierung der Definition, die die Tatsache nausnutzt , dass die ersten Divisorsummen immer ausreichen, um die ndritte Ziffer zu bestimmen . Wie immer ist die Lesereihenfolge von Mathematica ein bisschen komisch:

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

Dies erzeugt eine Liste mit allen Ergebnissen der Anwendung der unbenannten Funktion auf alle Werte ivon 1bis neinschließlich.

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

Wir beginnen damit, die Teiler von zu berechnen i, sie zu summieren Trund sich iselbst zu subtrahieren , sodass es sich nur um die Summe der Teiler handelt, die kleiner sind als i.

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

Dadurch wird das Ergebnis in eine Liste der Dezimalstellen umgewandelt.

##&@@...

Und dies entfernt den "Listen" -Kopf, so dass alle Ziffernlisten im Ergebnis von automatisch verkettet werden Array. Weitere Informationen zur Funktionsweise ##finden Sie im Abschnitt "Folgen von Argumenten" in diesem Beitrag .

...[[#]]

Schließlich wählen wir die ndritte Ziffer aus dem Ergebnis aus.

Martin Ender
quelle
4

Brachylog , 40 Bytes

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

Dies ist 1-indiziert, dauert etwa 0,15 Sekunden für N = 100, 15 Sekunden für N = 1000. Ich N = 10000laufe zurzeit für . Ich melde die Laufzeit, sobald sie endet. (Wenn meine Schätzung korrekt ist, sollte es ungefähr 8 Stunden dauern.)

Bearbeiten : Durch Beheben der Ausbreitung vorzeitiger Einschränkungen in Brachylog dauert es jetzt (bei einem 3 Byte längeren Code) ungefähr 2.5Minuten, 10000aber es wird ein out of global stackFehler zurückgegeben.

Erläuterung

  • Hauptprädikat: 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
    
  • Prädikat 1: berechnet die Summe der Teiler

    :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
    
  • Prädikat 2: Vereinheitlicht die Ausgabe mit einem Teiler der Eingabe

    >.>0,                 Output is a number between Input and 0
         ?:.%0            Input is divisible by Output
    
Tödlich
quelle
1
Mit der -GOption können Sie mehr globalen Stapel zuweisen . Der Standard ist nur 128M. Sie können zum Beispiel verwenden: swipl -G2Gum 2 GO zu verwenden.
Mat
4

Pyth, 26 21 20 15 Bytes

@sm`sf!%dTtUdSh

Probieren Sie es online aus. Testsuite.

Verwendet eine 0-basierte Indizierung. Das Programm ist O (n²) und ist für n = 9999 in ungefähr 14 Minuten auf meiner 2008-Maschine beendet.

PurkkaKoodari
quelle
Was ist los mit dieser komplizierten Teilersuche? f!%dTr1dist viel kürzer (aber auch langsamer)
Jakube
@ Jakube whoops, hat die falsche Version für die 20-Byte-Lösung geändert.
PurkkaKoodari
f!%TYtUTist das, was ich früher hatte.
PurkkaKoodari
@Jakube Ich habe das geändert. Es läuft noch für n = 9999, war jetzt über 5 Minuten: \
PurkkaKoodari
4

Jelly, 13 11 10 Bytes

2 Bytes dank @Adnan und 1 dank @Dennis.

ÆDṖSDµ€Fị@

Probieren Sie es online!

Verwendet 1-basierte Indizierung. Wird für n = 10000 in weniger als 2 Sekunden online ausgeführt.

PurkkaKoodari
quelle
ÆDṖSDµ€Fị@Speichert ein Byte.
Dennis
@Dennis gilt das also für die gesamte erste Kette?
PurkkaKoodari
@ Pietu1998: Ja, genau: Im Allgemeinen wird zur Analysezeit auf angewendet chain.pop() if chain else chains.pop(). Die neu gestartete Kette ist leer, daher wird stattdessen die zuletzt beendete Kette verwendet.
Lynn
3

PHP, 90 Bytes

0 indiziert

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

Absolut nicht subtil oder mit einer geschickten Herangehensweise.
Außerdem werden wie üblich drei Meldungen erzeugt, die ignoriert werden.

user55641
quelle
3

J , 34 Bytes

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

Dies ist nullindexiert und verwendet die folgende Formel, um die Divisorsummen zu berechnen.

Formel

Erläuterung

{[:;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
Meilen
quelle
2

MATL , 16 15 Bytes

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

Die Indizierung basiert auf 1.

Im Online-Compiler tritt eine Zeitüberschreitung des letzten Testfalls auf, aber mit dem Offline-Compiler wird in etwa 15 Sekunden das richtige Ergebnis erzielt.

Probieren Sie es 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
Luis Mendo
quelle
2

Haskell, 52 Bytes

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

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

Es ist eine direkte Implementierung der Definition: foreach nsum it divisors und konvertieren Sie es in eine Zeichenfolge. Verketten Sie alle diese Zeichenfolgen und wählen Sie das Element am gewünschten Index aus. Haskells Faulheit nimmt nur so viel ns von der unendlichen Liste [1..]wie nötig.

nimi
quelle
1

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]

Ziemlich unkomplizierte Implementierung der im Beitrag beschriebenen Methode.

Probieren Sie es online! (Ideone)

Wird im Online-Compiler nicht innerhalb der zugewiesenen 5 Sekunden für die Eingabe beendet 10000, wird aber auf meinem Computer für dieselbe Eingabe innerhalb von ca. 8,5 Sekunden beendet.

R. Kap
quelle
1

Oktave, 71 Bytes

Dieser ist nur Oktave. In MATLAB funktioniert es nicht. Es wird eine virtuelle Funktion erstellt, die mit 1-indizierten Zahlen arbeitet. Es kann wahrscheinlich ein bisschen weiter vereinfacht werden. Werde heute abend mal schauen.

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

Sie können es hier online versuchen .

Führen Sie einfach den obigen Befehl mit dem Präfix a=oder was auch immer aus (nur damit Sie ihn mehrmals verwenden können) und führen Sie dann a(10000)oder was auch immer aus. Es dauert ungefähr 7 Sekunden, um zu berechnen, dass die 10000ste Ziffer eine 7 ist.

Tom Carpenter
quelle
1

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);}

Zumindest ist es schnell. Es dauert durchschnittlich 0,3 Sekunden, um das 9999/10000-te Element auf meinem Computer zu erhalten. Es werden nur so viele Aliquotsummen generiert, wie Sie im Index angegeben haben. Dies bedeutet, dass die Zeichenfolge in den meisten Fällen etwas länger als Ihr Index ist, da einige Aliquotsummen 2 oder mehr Stellen haben, aber zum größten Teil nur so lange Zeichenfolgen generiert werden, wie wir benötigen.

Verwendung:

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);
}
Justin
quelle