Divisor de números ricos y pobres

18

Introducción

En el extraño mundo de los números enteros, los divisores son como activos y suelen llamar "ricos" a los números que tienen más divisores que su inversión, mientras que llaman a los "pobres" los que tienen menos divisores que su inversión.

Por ejemplo, el número tiene cinco divisores: , mientras que su inversión, , tiene solo cuatro: . Entonces se llama un número rico , mientras que un número pobre .24011,7,49,343,240110421,2,521,1042
24011042

Dada esta definición, podemos crear las siguientes dos secuencias enteras de números ricos y pobres:

(here we list the first 25 elements of the sequences)

 Index | Poor | Rich
-------|------|-------
     1 |   19 |   10
     2 |   21 |   12
     3 |   23 |   14
     4 |   25 |   16
     5 |   27 |   18
     6 |   29 |   20
     7 |   41 |   28
     8 |   43 |   30
     9 |   45 |   32
    10 |   46 |   34
    11 |   47 |   35
    12 |   48 |   36
    13 |   49 |   38
    14 |   53 |   40
    15 |   57 |   50
    16 |   59 |   52
    17 |   61 |   54
    18 |   63 |   56
    19 |   65 |   60
    20 |   67 |   64
    21 |   69 |   68
    22 |   81 |   70
    23 |   82 |   72
    24 |   83 |   74
    25 |   86 |   75
   ... |  ... |  ...

Notas:

  • como "inversión" de un número nos referimos a su inversión digital , es decir, tener sus dígitos en base 10 invertidos. Esto significa que los números que terminan con uno o más ceros tendrá un "corto" inversión: por ejemplo, la inversión de 1900es 0091por lo tanto91
  • excluimos intencionalmente los números enteros que tienen el mismo número de divisores que su inversión, es decir, los que pertenecen a OEIS: A062895

Desafío

Teniendo en cuenta las dos secuencias definidas anteriormente, su tarea es escribir un programa o función que, dado un número entero n(puede elegir 0 o 1 indexado), devuelve el enésimo número pobre y el enésimo número rico.

Entrada

  • Un número entero ( >= 0si está indexado a 0 o >= 1si está indexado a 1)

Salida

  • 2 enteros, uno para la secuencia pobre y otro para la secuencia rica, en el orden que prefiera siempre que sea consistente

Ejemplos:

INPUT          |   OUTPUT
----------------------------------
n (1-indexed)  |   poor    rich
----------------------------------
1              |   19      10
18             |   63      56
44             |   213     112
95             |   298     208
4542           |   16803   10282
11866          |   36923   25272
17128          |   48453   36466
22867          |   61431   51794
35842          |   99998   81888

Reglas generales:

  • Este es el , por lo que la respuesta más corta en bytes gana.
    No permita que los lenguajes de código de golf lo desalienten de publicar respuestas con idiomas que no sean de código. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación.
  • Las reglas estándar se aplican a su respuesta con las reglas de E / S predeterminadas , por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
  • Las lagunas predeterminadas están prohibidas.
  • Si es posible, agregue un enlace con una prueba para su código (es decir, TIO ).
  • Además, se recomienda agregar una explicación para su respuesta.
digEmAll
fuente
2
Conjetura: el º número de pobres es siempre mayor que el º número de ricos. Si alguien puede probar esto, probablemente reducirá los bytes de muchas respuestas. nnn
Robin Ryder
@RobinRyder: sospecho que es cierto, pero probar que es una historia completamente diferente :)
digEmAll
@RobinRyder Tenga en cuenta que varios números pueden mapearse a los mismos números revertidos debido a ceros a la izquierda (por ejemplo, 51, 510, 5100 todos se mapean a 15). Por cada número , habrá un número infinito de números revertidos correspondientes más ricos con ceros finales (con factores adicionales de , etc.), mientras que solo una cantidad finita de números revertidos más pobres. No creo que esto lo demuestre por completo (tal vez haya una cadena afortunada de números pobres en algún punto más adelante), pero al menos especifica que hay muchos más números ricos que pobres. 10 , 100 , 1000n10,100,1000
Jo King
2
@JoKing "... muchos más números ricos que pobres". Podría querer aclarar esta afirmación; tal como está escrito, podría interpretarse como que dice que el conjunto de números ricos tiene mayor cardinalidad que el conjunto de números pobres. Pero, por supuesto, ambos conjuntos son infinitamente contables (ninguna de las secuencias termina): es suficiente demostrar que hay infinitos primos cuyo primer dígito es a 2. Para esto, vea el Corolario 1.4 al final del siguiente documento, con el nmismo 19, 199, 1999, ...: m-hikari.com/ijcms-password/ijcms-password13-16-2006/…
mathmandan

Respuestas:

9

05AB1E , 16 bytes

∞.¡ÂÑgsÑg.S}¦ζsè

Pruébalo en línea!


0 indexado [rico, pobre]:

∞                # Push infinite list.
 .¡        }     # Split into three lists by...
   ÂÑgsÑg.S      # 1 if rich, 0 if nothing, -1 if poor.
            ¦ζ   # Remove list of nothings, and zip rich/poor together.
              sè # Grab nth element.

Tal vez alguien pueda explicar por qué esta versión no parece terminar, pero cuando hago clic en "cancelar ejecución" en TIO, finaliza con la respuesta correcta, o si espera 60 segundos, obtiene la respuesta correcta. Para una versión que termina "correctamente", podría usar: T+nL.¡ÂÑgsÑg.S}¦ζsè+3 bytes

Urna de pulpo mágico
fuente
Split-by no parece funcionar muy bien con infinitas listas.
Emigna
@Emigna personalmente, no tengo idea de cómo son posibles listas infinitas.
Urna mágica de pulpo
Evaluación perezosa. No calcules el número que no necesitas. Entonces ∞n5èsolo calcularía los primeros 6 números. Creo que cuando entran en juego estos tipos de construcciones de bucle / agrupación / división, la evaluación diferida falla e intenta calcular todos los elementos antes de regresar.
Emigna
1
Todavía creo que debería haber un byte incorporado para €g... Lo usé muy a menudo. Habría guardado un byte aquí con la alternativa (ahora igual byte) ‚рgÆ.±. Buena respuesta sin embargo! Gran uso de !
Kevin Cruijssen
@KevinCruijssen otro 2 byte para eso es δgjajaja.
Urna de pulpo mágico
6

JavaScript (ES6),  121 115 113  111 bytes

La entrada está indexada en 1. Salidas como [poor, rich].

x=>[(s=h=(n,i=x)=>i?h(++n,i-=(g=(n,k=n)=>k&&!(n%k)*~-s+g(n,k-1))(n)>g([...n+''].reverse().join``)):n)``,h(s=2)]

Pruébalo en línea!

Comentado

Función auxiliar

g = (n,                   // g is a helper function taking n and returning either the
        k = n) =>         // number of divisors or its opposite; starting with k = n
  k &&                    // if k is not equal to 0:
    !(n % k)              //   add either 1 or -1 to the result if k is a divisor of n
    * ~-s                 //   use -1 if s = 0, or 1 if s = 2
    + g(n, k - 1)         //   add the result of a recursive call with k - 1

Principal

x => [                    // x = input
  ( s =                   // initialize s to a non-numeric value (coerced to 0)
    h = (n,               // h is a recursive function taking n
            i = x) =>     // and using i as a counter, initialized to x
      i ?                 // if i is not equal to 0:
        h(                //   do a recursive call ...
          ++n,            //     ... with n + 1
          i -=            //     subtract 1 from i if:
            g(n)          //       the number of divisors of n (multiplied by ~-s within g)
            >             //       is greater than
            g(            //       the number of divisors of the reversal of n obtained ...
              [...n + ''] //         ... by splitting the digits
              .reverse()  //             reversing them
              .join``     //             and joining back
            )             //       (also multiplied by ~-s within g)
        )                 //   end of recursive call
      :                   // else:
        n                 //   we have reached the requested term: return n
  )``,                    // first call to h for the poor one, with n = s = 0 (coerced)
  h(s = 2)                // second call to h for the rich one, with n = s = 2
]                         // (it's OK to start with any n in [0..9] because these values
                          // are neither poor nor rich and ignored anyway)
Arnauld
fuente
4

Jalea , 22 bytes

ṚḌ;⁸Æd
Ç>/$Ɠ©#żÇ</$®#Ṫ

Pruébalo en línea!

n

Explicación

ṚḌ;⁸Æd | Helper link: take an integer and return the count of divisors fof its reverse and the original number in that order

Ṛ      | Reverse
 Ḍ     | Convert back from decimal digits to integer
  ;⁸   | Concatenate to left argument
    Æd | Count divisors


Ç>/$Ɠ©#żÇ</$®#Ṫ | Main link

    Ɠ©          | Read and evaluate a line from stdin and copy to register
   $  #         | Find this many integers that meet the following criteria, starting at 0 and counting up
Ç               | Helper link
 >/             | Reduce using greater than (i.e. poor numbers)
       ż        | zip with
           $®#  | Find the same number of integers meeting the following criteria
        Ç       | Helper link
         </     | Reduce using less than (i.e. rich numbers)
              Ṫ | Finally take the last pair of poor and rich numbers
Nick Kennedy
fuente
4

Wolfram Language (Mathematica) , 152 bytes

(a=b=k=1;m=n={};p=AppendTo;While[a<=#||b<=#,#==#2&@@(s=0~DivisorSigma~#&/@{k,IntegerReverse@k++})||If[#<#2&@@s,m~p~k;a++,n~p~k;b++]];{m[[#]],n[[#]]}-1)&

Pruébalo en línea!

Si la conjetura es cierta, entonces esta solución de 140 bytes también funciona

(a=k=1;m=n={};p=AppendTo;While[a<=#,#==#2&@@(s=0~DivisorSigma~#&/@{k,IntegerReverse@k++})||If[#<#2&@@s,m~p~k;a++,n~p~k]];{m[[#]],n[[#]]}-1)&   

Pruébalo en línea!

Aquí hay una trama pobre vs rica

ingrese la descripción de la imagen aquí

J42161217
fuente
¿Cuál es ese punto donde se acercan realmente?
Jo King
1
@JoKing, creo que esa(27635)= {70003, 65892}
J42161217
1
¡Excelente! Por cierto, esta es probablemente una de las pocas soluciones (quizás la única) capaz de alcanzar n = 35842 en TIO :)
digEmAll
3

Perl 6 , 81 bytes

{(*>*,* <*).map(->&c {grep
{[[&c]] map {grep $_%%*,1..$_},$_,.flip},1..*})»[$_]}

Pruébalo en línea!

  • * > *es una función anónima que devuelve verdadero si su primer argumento es mayor que el segundo. Del mismo modo para * < *. El primero seleccionará los números que pertenecen a la secuencia rica, el último seleccionará los que pertenecen a la secuencia pobre.
  • (* > *, * < *).map(-> &c { ... }) produce un par de secuencias infinitas, cada una basada en una de las funciones de comparación: la secuencia rica y la secuencia pobre, en ese orden.
  • »[$_]indexa en ambas secuencias usando $_, el argumento de la función de nivel superior, devolviendo una lista de dos elementos que contiene el $_miembro th de la secuencia rica y el $_miembro th de la secuencia pobre.
  • grep $_ %% *, 1..$_produce una lista de los divisores de $_.
  • map { grep $_ %% *, 1..$_ }, $_, .flipproduce una lista de dos elementos de los divisores de $_, y los divisores de $_con sus dígitos invertidos ("invertidos").
  • [[&c]]reduce esa lista de dos elementos con la función de comparación &c(ya sea mayor o menor que), produciendo un valor booleano que indica si este número pertenece a la secuencia rica de la secuencia pobre.
Sean
fuente
1..$_puede ser ^$_. También puede mover [$_]al interior de la función de mapa. 78 bytes
Jo King
3

Python 2 , 142 141 bytes

f=lambda i,n=1,a=[[],[]]:zip(*a)[i:]or f(i,n+1,[a[j]+[n]*(cmp(*[sum(x%y<1for y in range(1,x))for x in int(`n`[::-1]),n])==1|-j)for j in 0,1])

Pruébalo en línea!



Alternativa no recursiva (muy similar a las otras respuestas de Python)

Python 2 , 143 bytes

i=input()
a=[[],[]];n=1
while~i+len(zip(*a)):([[]]+a)[cmp(*[sum(x%i<1for i in range(1,x))for x in int(`n`[::-1]),n])]+=n,;n+=1
print zip(*a)[i]

Pruébalo en línea!

TFeld
fuente
3

Python 2 , 158153 bytes

-2 bytes gracias a shooqie

n=input()
p=[];r=[];c=1
while min(len(p),len(r))<=n:[[],r,p][cmp(*[sum(x%-~i<1for i in range(x))for x in c,int(str(c)[::-1])])]+=[c];c+=1
print p[n],r[n]

Pruébalo en línea!

La entrada está indexada en 0. Salidas como poor rich.

varilla
fuente
¿En +=[c]lugar de .append(c)trabajar?
shooqie
@shooqie Sería
Grimmy
2

Ruby , 128 bytes

La entrada está indexada a cero . Salidas como [pobre, rico].

->n,*a{b=[];i=0;d=->z{(1..z).count{|e|z%e<1}};(x=d[i+=1];y=d[i.digits.join.to_i];[[],b,a][x<=>y]<<i)until a[n]&b[n];[a[n],b[n]]}

Explicación

->n,*a{                             # Anonymous function, initialize poor array
       b=[];i=0;                    # Initialize rich array and counter variable
    d=->z{(1..z).count{|e|z%e<1}};  # Helper function to count number of factors
    (                               # Start block for while loop
     x=d[i+=1];                     # Get factors for next number
     y=d[i.digits.join.to_i];       # Factors for its reverse
                                    # (digits returns the ones digit first, so no reversing)
     [[],b,a][x<=>y]                # Fetch the appropriate array based on
                                    #  which number has more factors
                    <<i             # Insert the current number to that array
    )until a[n]&b[n];               # End loop, terminate when a[n] and b[n] are defined
    [a[n],b[n]]                     # Array with both poor and rich number (implicit return)
}                                   # End function

Pruébalo en línea!

Tinta de valor
fuente
2

Perl 6 , 76 bytes

{classify({+(.&h <=>h .flip)},^($_*3+99)){-1,1}[*;$_]}
my&h={grep $_%%*,^$_}

Pruébalo en línea!

No vi la respuesta de Sean Perl 6 , pero esto funciona de una manera diferente. Tenga en cuenta que he codificado el límite superior como n*3+99, lo que probablemente no sea estrictamente correcto. Sin embargo, podría reemplazar el *3con ³de no bytes adicionales, lo que haría el programa mucho menos eficiente, si más correcta.

Jo King
fuente
2

Icono , 180 175 bytes

procedure f(n)
a:=[];b:=[];k:=1
while{s:=t:=0 
i:=1to k+(m:=reverse(k))&(k%i=0&s+:=1)|(m%i=0&t+:=1)&\x
s>t&n>*a&push(a,k)
s<t&n>*b&push(b,k)
k+:=1;n>*a|n>*b}
return[!b,!a];end

Pruébalo en línea!

Galen Ivanov
fuente
2

APL (Dyalog Unicode) , 34 bytes

{⍵⌷⍉1↓⊢⌸{×-/{≢∪⍵∨⍳⍵}¨⍵,⍎⌽⍕⍵}¨⍳1e3}

Pruébalo en línea!

Gracias a Adám y ngn por ayudarme a jugar golf a esta monstruosidad.

TIO agota el tiempo de espera para los índices más grandes (que requieren ⍳1e5o ⍳1e6), pero con suficiente tiempo y memoria, la función terminará correctamente.

J. Sallé
fuente
2

R , 152 137 bytes

-12 bytes gracias a Giuseppe -3 bytes gracias a digEmAll

n=scan()
F=i=!1:2
`?`=sum
while(?n>i)if(n==?(i[s]=i[s<-sign((?!(r=?rev((T=T+1)%/%(e=10^(0:log10(T)))%%10)*e)%%1:r)-?!T%%1:T)]+1))F[s]=T
F

Pruébalo en línea!

Tes el entero que se está probando actualmente; Los últimos números pobres y ricos se almacenan en el vector F.

La forma más corta que pude encontrar de revertir un número entero fue convertirlo a dígitos en la base 10 con aritmética modular, y luego volver a convertir con potencias de 10 invertidas, pero espero ser superado en este y otros frentes.

Explicación (de la versión anterior, similar):

n=scan() # input
i=0*1:3  # number of poor, middle class, and rich numbers so far
S=sum
while(S(n>i)){ # continue as long as at least one of the classes has less than n numbers
  if((i[s]=i[
    s<-2+sign(S(!(           # s will be 1 for poor, 2 for middle class, 3 for rich
      r=S((T<-T+1)%/%10^(0:( # reverse integer T with modular arithmetic
        b=log10(T)%/%1       # b is number of digits
        ))%%10*10^(b:0)) 
      )%%1:r)-               # compute number of divisors of r
      S(!T%%1:T))            # computer number of divisors of T
    ]+1)<=n){                # check we haven't already found n of that class
    F[s]=T
  }
}
F[-2] # print nth poor and rich numbers
Robin Ryder
fuente
146 bytes ; no tengo idea de cuál es la respuesta de digEmAll
Giuseppe
@Giuseppe Gracias! Me encanta el uso de nchar.
Robin Ryder
142 bytes ; Tuve problemas con la precedencia del operador antes, pero lo desconcerté.
Giuseppe
2
¡Gran trabajo! 140 cambiando la estrategia inversa
digEmAll
2
@digEmAll 138 bytes volviendo a log10!
Giuseppe
1

JavaScript (Node.js) ,190 180 bytes

Salidas como [poor, rich].

n=>{let p,r,f=h=i=0;while(f<n){k=d(i),e=d(+(i+"").split``.reverse().join``);if(k<e){p=i;f++}if(k>e&&h<n){r=i;h++}i++}return[p,r]}
d=n=>{c=0;for(j=1;j<=n;j++)if(n%j==0)c++;return c}

Pruébalo en línea!

Explicación

d(n) Función

Este ayudante encuentra la cantidad de factores que tiene un número.

d=n=>{              // Equivalent to `function d(n) {
  c=0;              // Counter
  for(j=1;j<=n;j++) // Check every integer from 1 to n
    if(n%j==0)c++;  // If the number is a factor, add 1 to the counter
  return c
};

Función principal

n=>{ 
  let p,r,f=h=i=0; // p -> the poor number, r -> the rich number, f -> the number of poor numbers found, h -> the number of rich numbers found, i -> the current number being checked
  while(f<n){ // While it's found less than n poor numbers (assumes that it will always find the rich number first)
    k=d(i),        // k -> number of factors of i
    e=d(+((i+"").split``.reverse().join``)); // e -> number of factors of reversed i
    if(k<e){p=i;f++}  // If it hasn't found enough poor numbers and i is poor, save it and count it
    if(k>e&&h<n){r=i;h++}  // If it hasn't found enough rich numbers and i is rich, save it and count it
    i++
  };
  return[p,r]
}
Ian
fuente