Count how many numbers are divisible by perfect numbers in a given range

Question

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

• Vereos: 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).
• user12205: @Vereos the question says Count how many numbers are divisible by perfect numbers
• Vereos: Woah, I've been misleaded by the question's name. Thank you!
• Wasi: @Peter Taylor Arbitrary integers
• mniip: Well technically 1 is perfect...

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

C, (削除) 125 (削除ここまで)120

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, (削除) 212 (削除ここまで)209

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

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

Vyxal, 11 bytes

ṡƛ'∆K=;Ḋa;∑

Try it Online!

9 bytes with s flag

12 bytes accounting for space seperated inputs

Explained

ṡƛ'∆K=;Ḋa;∑
ṡƛ ; # Over each item x in the range [input a, input b]
 '∆K=; # Keep items from the range [1, x] that are perfect numbers
 Ḋa # And is x divisible by any of those perfect numbers?
 ∑ # Sum the number of numbers that are divisible by a perfect number