16
\$\begingroup\$

Introduction

In the strange world of integer numbers, divisors are like assets and they use to call "rich" the numbers having more divisors than their reversal, while they call "poor" the ones having less divisors than their reversal.

For example, the number \$2401\$ has five divisors : \$1,7,49,343,2401\$, while its reversal, \$1042\$, has only four : \$1,2,521,1042\$.
So \$2401\$ is called a rich number, while \$1042\$ a poor number.

Given this definition, we can create the following two integer sequences of rich and poor numbers :

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

Notes :

  • as "reversal" of a number we mean its digital reverse, i.e. having its digits in base-10 reversed. This means that numbers ending with one or more zeros will have a "shorter" reversal : e.g. the reversal of 1900 is 0091 hence 91
  • we intentionally exclude the integer numbers having the same number of divisors as their reversal i.e. the ones belonging to OEIS:A062895

Challenge

Considering the two sequences defined above, your task is to write a program or function that, given an integer n (you can choose 0 or 1-indexed), returns the n-th poor and n-th rich number.

Input

  • An integer number (>= 0 if 0-indexed or >= 1 if 1-indexed)

Output

  • 2-integers, one for the poor sequence and one for the rich sequence, in the order you prefer as long as it is consistent

Examples :

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

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.
\$\endgroup\$
  • 2
    \$\begingroup\$ Conjecture: the \$n\$th poor number is always greater than the \$n\$th rich number. If someone can prove this, it will probably shave bytes off many answers. \$\endgroup\$ – Robin Ryder May 15 at 19:57
  • \$\begingroup\$ @RobinRyder: I suspect that's true, but proving it is a whole different story :) \$\endgroup\$ – digEmAll May 15 at 20:10
  • \$\begingroup\$ @RobinRyder Consider that multiple numbers can map to the same reversed numbers due to leading zeroes (e.g. 51, 510, 5100 all map to 15). For every number \$n\$, there will be an infinite number of richer corresponding reversed numbers with trailing zeroes (with extra factors of \$10,100,1000\$,etc.), while only a finite amount of poorer reversed numbers. I don't think this fully proves it (maybe there's a lucky chain of poor numbers somewhere down the line), but it at least specifies that there are far more rich numbers than poor. \$\endgroup\$ – Jo King May 16 at 4:20
  • 2
    \$\begingroup\$ @JoKing "...far more rich numbers than poor." Might want to clarify this statement; as written it could be interpreted as saying that the set of rich numbers has greater cardinality than the set of poor numbers. But of course both sets are countably infinite (neither sequence terminates): it suffices to prove that there are infinitely many primes whose first digit is a 2. For this, see Corollary 1.4 at the end of the following paper, with n equal to 19, 199, 1999, ...: m-hikari.com/ijcms-password/ijcms-password13-16-2006/… \$\endgroup\$ – mathmandan May 16 at 21:57

13 Answers 13

9
\$\begingroup\$

05AB1E, 16 bytes

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

Try it online!


0-indexed [rich,poor]:

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

Maybe someone can explain why this version doesn't seem to terminate, but when I click "cancel execution" on TIO it finishes with the correct answer, or if you wait 60 seconds you get the correct answer. For a version that terminates "correctly" you could use: T+nL.¡ÂÑgsÑg.S}¦ζsè +3 bytes

\$\endgroup\$
  • \$\begingroup\$ Split-by doesn't seem to work very nicely with infinite lists. \$\endgroup\$ – Emigna May 15 at 21:14
  • \$\begingroup\$ @Emigna personally, I don't have any idea how infinite lists even are possible. \$\endgroup\$ – Magic Octopus Urn May 15 at 21:15
  • \$\begingroup\$ Lazy evaluation. Don't calculate number you don't need. So ∞n5è would only calculate the first 6 numbers. I think when these types of looping/grouping/splitting constructs come in to play, the lazy eval fails and it tries to calculate all items before returning. \$\endgroup\$ – Emigna May 15 at 21:24
  • 1
    \$\begingroup\$ I still think there should be a 1-byte builtin for €g.. I used it so often. Would have saved a byte here with the (now equal byte) alternative ‚рgÆ.±. Nice answer though! Great usage of ! \$\endgroup\$ – Kevin Cruijssen May 16 at 9:52
  • \$\begingroup\$ @KevinCruijssen another 2 byte for that is δg lol. \$\endgroup\$ – Magic Octopus Urn May 16 at 18:43
6
\$\begingroup\$

JavaScript (ES6),  121 115 113  111 bytes

Input is 1-indexed. Outputs as [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)]

Try it online!

Commented

Helper function

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

Main

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

Jelly, 22 bytes

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

Try it online!

A full program taking 1-indexed \$n\$ on stdin and returning a list of the n-th poor and rich integers in that order.

Explanation

ṚḌ;⁸Æ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
\$\endgroup\$
4
\$\begingroup\$

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

Try it online!

If the conjecture is true, then this 140 bytes solution also works

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

Try it online!

Here is poor vs rich plot

enter image description here

\$\endgroup\$
  • \$\begingroup\$ What's that point where they come really close? \$\endgroup\$ – Jo King May 16 at 9:59
  • 1
    \$\begingroup\$ @JoKing I believe it is a(27635)= {70003, 65892} \$\endgroup\$ – J42161217 May 16 at 10:20
  • 1
    \$\begingroup\$ Great! BTW, this is probably one of the few solutions (maybe the only one) able to reach n=35842 on TIO :) \$\endgroup\$ – digEmAll May 16 at 11:32
3
\$\begingroup\$

Perl 6, 81 bytes

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

Try it online!

  • * > * is an anonymous function that returns true if its first argument is greater than its second. Similarly for * < *. The former will select numbers that belong to the rich sequence, the latter will select those that belong to the poor sequence.
  • (* > *, * < *).map(-> &c { ... }) produces a pair of infinite sequences, each based on one of the comparator functions: the rich sequence and the poor sequence, in that order.
  • »[$_] indexes into both of those sequences using $_, the argument to the top-level function, returning a two-element list containing the $_th member of the rich sequence and the $_th member of the poor sequence.
  • grep $_ %% *, 1..$_ produces a list of the divisors of $_.
  • map { grep $_ %% *, 1..$_ }, $_, .flip produces a two-element list of the divisors of $_, and the divisors of $_ with its digits reversed ("flipped").
  • [[&c]] reduces that two-element list with the comparator function &c (either greater-than or less-than), producing a boolean value indicating whether this number belongs to the rich sequence of the poor sequence.
\$\endgroup\$
  • \$\begingroup\$ 1..$_ can be ^$_. You can also move the [$_] to inside the map function. 78 bytes \$\endgroup\$ – Jo King May 16 at 4:24
3
\$\begingroup\$

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

Try it online!



Non-recursive alternative (very similar to the other Python answers)

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]

Try it online!

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

Python 2, 158 153 bytes

-2 bytes thanks to 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]

Try it online!

Input is 0-indexed. Outputs as poor rich.

\$\endgroup\$
  • \$\begingroup\$ Would +=[c] instead of .append(c) work? \$\endgroup\$ – shooqie May 15 at 20:18
  • \$\begingroup\$ @shooqie It would \$\endgroup\$ – Grimy May 16 at 11:02
2
\$\begingroup\$

Ruby, 128 bytes

Input is zero-indexed. Outputs as [poor, rich].

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

Explanation

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 76 bytes

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

Try it online!

I didn't see Sean's Perl 6 answer, but this works in a different way. Note that I've hardcoded the upperbound as n*3+99, which is probably not strictly correct. However, I could replace the *3 with ³ for no extra bytes, which would make the program far less efficient, if more correct.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 152 bytes

def f(n):
 a,b=[],[];i=1
 while not(a[n:]and b[n:]):[[],b,a][cmp(*[sum(m%-~i<1for i in range(m))for m in i,int(`i`[::-1])])]+=[i];i+=1
 return a[n],b[n]

Try it online!

Ends up being pretty similar to Rod's answer. Returns zero-indexed nth poor, rich tuple.

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

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

Try it online!

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

JavaScript (Node.js), 190 180 bytes

Outputs as [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}

Try it online!

Explanation

d(n) Function

This helper finds the number of factors that a number has.

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

Main Function

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]
}
\$\endgroup\$
1
\$\begingroup\$

C# (Visual C# Interactive Compiler), 221 bytes

n=>{int g,h,i,j=9,k,l,m,o,r,p;m=o=r=p=0;while(m<n||o<n){k=g=h=0;l=++j;while(l!=0){k=k*10+l%10;l/=10;}for(i=2;i<j+k;i++){if(j%i<1&&i<j)g++;if(k%i<1&&i<k)h++;}if(g<h&&o<n){o++;p=j;}if(g>h&&m<n){m++;r=j;}}return new{n,p,r};}

Try it online!

\$\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.