Números ricos e pobres do divisor

18

Introdução

No mundo estranho dos números inteiros, os divisores são como ativos e costumam chamar de "ricos" os números que têm mais divisores do que a reversão, enquanto chamam de "pobres" os que têm menos divisores do que a reversão.

Por exemplo, o número 2401 possui cinco divisores: 1,7,49,343,2401 , enquanto sua reversão, 1042 , possui apenas quatro: 1,2,521,1042 .
Então 2401 é chamado de número rico , enquanto 1042 um número ruim .

Dada essa definição, podemos criar as duas seguintes seqüências inteiras de números ricos e 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 "reversão" de um número, queremos dizer seu reverso digital , ou seja, ter seus dígitos na base 10 invertidos. Isso significa que os números que terminam com um ou mais zeros terão uma reversão "mais curta": por exemplo, a reversão de 1900é, 0091portanto,91
  • intencionalmente, excluímos os números inteiros com o mesmo número de divisores que sua reversão, ou seja, os pertencentes à OEIS: A062895

Desafio

Considerando as duas seqüências definidas acima, sua tarefa é escrever um programa ou função que, dado um número inteiro n (você pode escolher 0 ou 1 indexado), retorne o n-ésimo número pobre e n-ésimo número.

Entrada

  • Um número inteiro ( >= 0se 0-indexado ou >= 1se 1-indexado)

Resultado

  • 2 inteiros, um para a sequência ruim e outro para a sequência rica, na ordem em que você preferir, desde que seja consistente

Exemplos :

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

Regras gerais:

  • Isso é , então a resposta mais curta em bytes vence.
    Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para 'qualquer' linguagem de programação.
  • As regras padrão se aplicam à sua resposta com as regras de E / S padrão , para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados e programas completos do tipo retorno. Sua chamada.
  • As brechas padrão são proibidas.
  • Se possível, adicione um link com um teste para o seu código (ou seja, TIO ).
  • Além disso, é altamente recomendável adicionar uma explicação para sua resposta.
digEmAll
fonte
2
Conjectura: o º número pobres é sempre maior do que o n º número rico. Se alguém puder provar isso, provavelmente reduzirá os bytes de muitas respostas. nn
Robin Ryder
@RobinRyder: Eu suspeito que isso seja verdade, mas provar que é uma história totalmente diferente :)
digEmAll
@RobinRyder Considere que vários números podem ser mapeados para os mesmos números invertidos devido aos zeros à esquerda (por exemplo, 51, 510, 5100, todos mapeados para 15). Para cada número , haverá um número infinito de números invertidos correspondentes mais ricos com zeros à direita (com fatores extras de 10 , 100 , 1000 , etc.), enquanto apenas uma quantidade finita de números invertidos mais pobres. Eu não acho que isso prova completamente (talvez exista uma cadeia de números ruins em algum lugar abaixo da linha), mas pelo menos especifica que há números muito mais ricos do que pobres. n10,100,1000
Jo King
2
@JoKing "... números muito mais ricos que pobres." Pode querer esclarecer esta afirmação; como está escrito, poderia ser interpretado como dizendo que o conjunto de números ricos tem maior cardinalidade do que o conjunto de números ruins. Mas é claro que ambos os conjuntos são contados infinitamente (nenhuma sequência termina): basta provar que existem infinitos primos cujo primeiro dígito é a 2. Para isso, consulte o Corolário 1.4 no final do documento a seguir, com nigual a 19, 199, 1999, ...: m-hikari.com/ijcms-password/ijcms-password13-16-2006/…
mathmandan

Respostas:

9

05AB1E , 16 bytes

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

Experimente online!


Indexado 0 [rico, ruim]:

∞                # 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.

Talvez alguém possa explicar por que essa versão parece não terminar, mas quando clico em "cancelar execução" no TIO, ela termina com a resposta correta ou, se você esperar 60 segundos, obtém a resposta correta. Para uma versão que termina "corretamente", você pode usar: T+nL.¡ÂÑgsÑg.S}¦ζsè+3 bytes

Urna de Polvo Mágico
fonte
A divisão por parece não funcionar muito bem com listas infinitas.
Emigna
@ Emigna, pessoalmente, eu não tenho nenhuma idéia de como listas infinitas são possíveis.
Magic Octopus Urn
Avaliação preguiçosa. Não calcule o número que você não precisa. Então ∞n5è, só calcularia os 6 primeiros números. Eu acho que quando esses tipos de construções de loop / agrupamento / divisão entram em cena, a avaliação preguiçosa falha e tenta calcular todos os itens antes de retornar.
Emigna
1
Eu ainda acho que deveria haver um byte embutido para €g.. Eu o usei com tanta frequência. Teria salvo um byte aqui com a alternativa (agora igual byte) ‚рgÆ.±. Boa resposta embora! Ótimo uso de !
Kevin Cruijssen
@KevinCruijssen outro byte 2 para isso é δglol.
Magic Octopus Urn
6

JavaScript (ES6),  121 115 113  111 bytes

A entrada é indexada em 1. Saídas 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)]

Experimente online!

Comentado

Função 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

a 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
fonte
4

Gelatina , 22 bytes

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

Experimente online!

n

Explicação

ṚḌ;⁸Æ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
fonte
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)&

Experimente online!

Se a conjectura for verdadeira, essa solução de 140 bytes também funcionará

(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)&   

Experimente online!

Aqui está o enredo ruim versus rico

insira a descrição da imagem aqui

J42161217
fonte
Qual é o ponto em que eles chegam realmente perto?
Jo King
1
@JoKing Eu acredito que éa(27635)= {70003, 65892}
J42161217
1
Ótimo! BTW, esta é provavelmente uma das poucas soluções (talvez a única) capaz de atingir n = 35842 no TIO :)
digEmAll
3

Perl 6 , 81 bytes

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

Experimente online!

  • * > *é uma função anônima que retorna true se o primeiro argumento for maior que o segundo. Da mesma forma para * < *. O primeiro selecionará números que pertencem à sequência rica, o último selecionará aqueles que pertencem à sequência ruim.
  • (* > *, * < *).map(-> &c { ... }) produz um par de sequências infinitas, cada uma baseada em uma das funções do comparador: a sequência rica e a sequência ruim, nessa ordem.
  • »[$_]indexa as duas seqüências usando $_, o argumento para a função de nível superior, retornando uma lista de dois elementos contendo o $_th membro da sequência rich e o $_th membro da sequência pobre.
  • grep $_ %% *, 1..$_produz uma lista dos divisores de $_.
  • map { grep $_ %% *, 1..$_ }, $_, .flipproduz uma lista de dois elementos dos divisores de $_e os divisores de $_com seus dígitos invertidos ("invertido").
  • [[&c]]reduz essa lista de dois elementos com a função comparadora &c(maior que ou menor que), produzindo um valor booleano indicando se esse número pertence à sequência rica da sequência ruim.
Sean
fonte
1..$_pode ser ^$_. Você também pode mover o [$_]para dentro da função 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])

Experimente online!



Alternativa não recursiva (muito semelhante às outras respostas do 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]

Experimente online!

TFeld
fonte
3

Python 2 , 158 153 bytes

-2 bytes graças 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]

Experimente online!

A entrada é indexada em 0. Saídas como poor rich.

Cajado
fonte
Em +=[c]vez de .append(c)trabalhar?
shooqie
@shooqie Seria
Grimmy
2

Rubi , 128 bytes

A entrada é indexada a zero . Resultados como [ruim, 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]]}

Explicação

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

Experimente online!

Value Ink
fonte
2

Perl 6 , 76 bytes

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

Experimente online!

Não vi a resposta Perl 6 de Sean , mas isso funciona de uma maneira diferente. Observe que eu codifiquei o upperbound como n*3+99, o que provavelmente não é estritamente correto. No entanto, eu poderia substituir o *3com ³para não bytes extras, o que tornaria o programa muito menos eficiente, se mais correto.

Brincadeira
fonte
2

Ícone , 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

Experimente online!

Galen Ivanov
fonte
2

APL (Dyalog Unicode) , 34 bytes

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

Experimente online!

Agradeço a Adám e à ngn por me ajudarem a jogar golfe nessa monstruosidade.

O TIO atinge o tempo limite para os índices maiores (que exigem ⍳1e5ou ⍳1e6), mas, com tempo e memória suficientes, a função termina corretamente.

J. Sallé
fonte
2

R , 152 137 bytes

-12 bytes graças a Giuseppe -3 bytes graças 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

Experimente online!

Té o número inteiro atualmente sendo tentado; os últimos números pobres e ricos são armazenados no vetor F.

A maneira mais curta que eu pude encontrar de reverter um número inteiro foi convertê-lo em dígitos na base 10 com aritmética modular e depois converter com potências de 10 invertidas, mas espero ser superado nesta e em outras frentes.

Explicação (da versão anterior e 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
fonte
146 bytes ; não faço ideia qual é a resposta do digEmAll
Giuseppe
@Giuseppe Thanks! Eu amo o uso de nchar.
Robin Ryder
142 bytes ; Eu tive problemas com a precedência do operador antes, mas fiquei intrigado.
Giuseppe
2
Bom trabalho! 140 mudando a estratégia reversa
digEmAll
2
@digEmAll 138 bytes retornando a log10!
Giuseppe
1

JavaScript (Node.js) ,190 180 bytes

Saídas 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}

Experimente online!

Explicação

d(n) Função

Esse auxiliar encontra o número de fatores que um número possui.

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

Função 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
fonte