6
\$\begingroup\$

Given two arbitrary integers \$a\$ and \$b\$, count how many numbers are divisible by perfect numbers in that given range (\$a\$ and \$b\$ both are inclusive).

In mathematics, a perfect number is a positive integer that is the sum of its proper positive divisors, that is, the sum of the positive divisors excluding the number itself.Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself), or \$σ(n) = 2n\$.

Input:

1 100

Output:

18
  • Use stdin and stdout for Input/Output
  • Your code must handle big integers, so it is not good enough to hard-code a list of perfect numbers.
  • Shortest code wins
\$\endgroup\$
12
  • \$\begingroup\$ 18 is not a perfect number! I guess you meant 28? (Since 18!=9+6+3+2+1, while 28=14+7+4+2+1). \$\endgroup\$
    – Vereos
    Jan 17, 2014 at 9:17
  • \$\begingroup\$ @Vereos the question says Count how many numbers are divisible by perfect numbers \$\endgroup\$
    – user12205
    Jan 17, 2014 at 9:27
  • \$\begingroup\$ Woah, I've been misleaded by the question's name. Thank you! \$\endgroup\$
    – Vereos
    Jan 17, 2014 at 9:29
  • \$\begingroup\$ @Peter Taylor Arbitrary integers \$\endgroup\$
    – Wasi
    Jan 17, 2014 at 9:37
  • 1
    \$\begingroup\$ Well technically 1 is perfect... \$\endgroup\$
    – mniip
    Jan 17, 2014 at 14:22

7 Answers 7

3
\$\begingroup\$

Perl 6, 106 103 characters

my ($a,$b)=get.words;(($a..$b).grep: *%%any ($a..$b).grep: {$^n==[+] ($^n%%$_&&$_ for 1..^$^n)})[*.say]

There's a lot of syntax here, so hopefully this explanation helps at least a little to someone who knows a bit of Perl 5 syntax, though I won't explain every detail:

Finds all the perfect numbers in the range $a..$b: ($a..$b).grep: {$^n==[+] ($^n%%$_&&$_ for 1..^$^n)} (explained below). It then chooses all the numbers in the range $a..$b which are divisible (%%) by any of the perfect numbers it had found: (%a..%b).grep: * %% any ….

The final (…)[*.say] abuses the fact that any code (in this case *.say, which prints its argument and a newline) passed to the […] postfix will be given the list's length as its argument (so that one can, e.g., use the idiomatic @array[*-1] to get the last element of @array). This means that the (…)[*.say] here has the same effect as say (…).elems.

The part that finds all the perfect numbers in the range does so by returning only those numbers which are equal ($^n ==) to the sum of their divisors. [+] adds together the values following it, for 1..^$^n iterates over all numbers 1 to $^n-1 and assigns $_ to them, and $^n %% $_ && $_ returns $_ if $^n is divisible ($^n %% $_) by $_, or else False, thus creating a list that consists of the proper divisors of $^n and False objects, which numify to 0 when all the values are added together by [+].

Perl 6 uses arbitrary sized integers, so, if you have the resources and the time, it could technically compute for big integers

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

Mathematica - 117

Naive approach, linear for the range size

With[{p=#(#+1)/2&/@Select[2^Range@@Floor@Log2@Sqrt@#-1,PrimeQ]},Length@Select[Range@@#,Or@@Divisible[#,p]&]]&@Input[]

The correct way would be constructing numbers from the perfect numbers that are in the given range of course.

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

Haskell - 157

c x=x==sum[i|i<-[1..x-1],mod x i==0]
d x=any((0==).mod x)$takeWhile(<=x)(filter c[2..])
main=do m<-getLine;n<-getLine;print$length(filter d[read m..read n])

Can work with arbitrarily large numbers given respectively large time.
Input is given on 2 lines.

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

C, 125120

a,b,c,p[4]={6,28,496,8128};main(i){for(scanf("%d%d",&a,&b);a<=b;a++)for(i=0;i<4;)if(a%p[i++]==0)c++,i=4;printf("%d",c);}

A little more readable:

a,b,c=0,i,p[4]={6,28,496,8128};
main()
{
    for(scanf("%d%d",&a,&b);a<=b;a++)
        for(i=0;i<4;)
            if(a%p[i++]==0)
            {
                c++;
                i=4;
            }
    printf("%d",c);
}

This works with signed 32bit integers, up to 2^31-1=2147483647.

C, 212209

#include<stdint.h>
uint64_t a,b,c,p[8]={6,28,496,8128,33550336,8589869056,137438691328,0x1fffffffc0000000};main(i){for(scanf("%lld%lld",&a,&b);a<=b;a++)for(i=0;i<8;)if(a%p[i++]==0)c++,i=8;printf("%lld",c);}

Should work up to 2^64-1=18446744073709551615.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ In C global ints are initialized to 0 by default so you don't need to set c=0 :) \$\endgroup\$
    – Josh
    Jan 19, 2014 at 0:52
  • 1
    \$\begingroup\$ To save 1 char you could move one of your ints into the main declaration, ex main(i) (saves a comma character). \$\endgroup\$
    – Josh
    Jan 19, 2014 at 0:53
  • \$\begingroup\$ Oh, you're right! I also removed a couple of useless {}. \$\endgroup\$
    – izabera
    Jan 19, 2014 at 1:08
  • \$\begingroup\$ You can remove the pair of braces around your if statement by changing the contents to be c++,i=4; \$\endgroup\$
    – Josh
    Jan 19, 2014 at 1:49
  • \$\begingroup\$ Yes, I did it. Well, not in the prettified version, but that's not supposed to be short, isn't it? \$\endgroup\$
    – izabera
    Jan 19, 2014 at 2:24
2
\$\begingroup\$

Python 3 [166 bytes]

a,b=map(int,input().split());print(len(set([n if n%p==0 else 0 for p in [x for x in range(a,b) if sum(y for y in range(1,x) if x%y==0)==x] for n in range(a,b+1)]))-1)

More readable:

// STDIN => a, b
a, b = map(int, input().split())

// list of perfect numbers
perfect = [x for x in range(a, b) if sum(y for y in range(1, x) if x % y == 0) == x]

// length(number % [any perfect number] == 0) => STDOUT
print(len(set([n if n % p == 0 else 0 for p in perfect for n in range(a, b + 1)])) - 1)

Here the list of perfect numbers is calculated inline but may be set statically. The number range should be bound by the machine's word size.

While this algorithm is deadly slow and takes ages for working with big numbers, it is at least short :)

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

Jelly, 10 bytes

rÆD=Æṣ$§TL

Try it online!

Requiring space separated STDIN input bumps the byte count up to 15 bytes

How it works

rÆD=Æṣ$§TL - Main link. Takes a on the left and b on the right
r          - Yield [a, a+1, ..., b-1, b]
 ÆD        - Generate the divisors of each
      $    - Over each list of divisors, d:
    Æṣ     -   Generate the proper divisor sum of each value in d
   =   §   -   Count how many are equal to their proper divisor sum
             This maps numbers with perfect to divisors to a non-zero value
             and those without to 0
        TL - Count the number of non-zero elements
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -MList::Util=sum,any -pl, 77 bytes

$"=$_,$\+=any{$"%$_==0}grep{//;2*$_==sum grep{$'%$_==0}1..$_}2..$"for$_..<>}{

Try it online!

Ungolfed:

$_ = ; # implicit by -p command line switch
for$_($_..){ # loop over the range from $_ to the next input
   $"=$_;                           # store a copy of the current number ($_) so it can be used in sub-loops
   $\+=                             # counter for number of perfectly divisible numbers found
      any{$"%$_==0}                 # check if the current number ($") is evenly divisible by a:
         grep{//;2*$_==             # PERFECT NUMBER: a number where twice the number equals
            sum grep{$'%$_==0}1..$_ #                 the sum of the numbers which divide it evenly
         }2..$"                     # that exists in range of 2 to the current number
}
print$\; # implicit by -p command line switch
\$\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.