# Find primitive semiperfect numbers

## Semiperfect numbers

A semiperfect/pseudoperfect number is an integer equal to the sum of a part of or all of its divisors (excluding itself). Numbers which are equal to the sum of all of their divisors are perfect.

Divisors of 6 : 1,2,3
6 = 1+2+3 -> semiperfect (perfect)
Divisors of 28 : 1,2,4,7,14
28 = 14+7+4+2+1 -> semiperfect (perfect)
Divisors of 40 : 1,2,4,5,8,10,20
40 = 1+4+5+10+20 or 2+8+10+20 -> semiperfect


## Primitive

A primitive semiperfect number is a semiperfect number with no semiperfect divisors (except itself :))

Divisors of 6 : 1,2,3
6  = 1+2+3 -> primitive
Divisors of 12 : 1,2,3,4,6
12 = 2+4+6 -> semiperfect


As references, please use the OEIS series A006036 for primitive semiperfect numbers, and A005835 for semiperfects.

## Goal

Write a program or a function in any language. It will take as input a number n as a function parameter or from STDIN/your language's closest alternative, and will output all the primitive semi-perfect numbers from 1 to n (inclusive).

The output must be formated as 6[separator]20[separator]28[separator]88... where [separator] is either as newline, a space or a comma. There must not be a starting [separator] nor a ending one.

Edit : you can leave a trailing newline

## Examples

input :

5


output :

input :

20


output :

6
20


input :

100


output :

6 20 28 88


## Scoring

This is code-golf, so the shortest code in bytes win.

Don't try to fool us with loopholes please :).

I'd be glad you could leave an explanation of your golfed code once you think you're done golfing it!

# Pyth, 28 27 bytes

VQI}KhNsMyJf!%KTSNI!@JYeaYK


1 byte thanks to @Jakube

Demonstration.

VQI}KhNsMyJf!%KTSNI!@JYeaYK
Implicit:
Y = []
Q = eval(input())
VQ                              for N in range(Q):
KhN                         K = N+1
f    SN              filter T over range(1, N)
!%KT                the logical not of K%T.
This is the list of divisors of K.
J                     Store the list in J.
y                      Create all of its subsets.
sM                       Map each subset to its sum.
I}K                           If K is in that list: (If K is semiperfect)
I!@JY         If the intersection of J (the divisors)
and Y (the list of primitive semiperfect numbers)
is empty:
aYK     Append K to Y
e        And print its last element, K.

• @AlexA. Thanks! It is necessary to append K to Y to build Y, which is needed elsewhere. However, I could do the printing separately, such as with aYKK instead of eaYK. It's 4 bytes either way, however. – isaacg Jun 19 '15 at 15:03

# Jelly, 22 bytes

ÆDṖŒPS€i
ÆDÇ€TL’
RÇÐḟY


Try it online!

Explanation

ÆDṖŒPS€i - helper function to check if input is a semiperfect number
ÆD       - list of divisors of input
Ṗ      - except for the last one (the input)
ŒP    - power set = every possible subset of divisors
S€  - sum of each subset
i - return truthy iff input is one of these

ÆDÇ€TL’ - helper function to check if input is a primitive semiperfect number
ÆD       - list of divisors of input
Ç€     - replace each with if they are a semiperfect number, based on
the above helper function. If input is a primitive semiperfect
number, we get something like [0,0,0,0,0,94].
T    - get all truthy values.
L’  - return falsy iff there is only one truthy value

R        - Range[input]
ÇÐḟ     - Filter out those elements which are not primitive semiperfect
numbers, based on the helper function
Y    - join by newlines.


# JavaScript (ES6) 172

Run the snippet below to test

f=
v=>eval("for(n=h=[];n++<v;!t*i&&n>1?h[n]=1:0){for(r=[l=i=t=1];++i<n;)n%i||(h[i]?t=0:l=r.push(i));for(i=0;t&&++i<1<<l;)r.map(v=>i&(m+=m)?t-=v:0,t=n,m=.5)}''+Object.keys(h)")

// Less golfed

ff=v=>
{
h=[]; // hashtable with numbers found so far

for (n=1; n <= v; n++)
{
r=[1],l=1; // r is the list of divisors, l is the length of this list
t=1; // used as a flag, will become 0 if a divisor is in h
for(i=2; i<n; i++)
{
if (n%i == 0)
if (h[i])
t = 0; // found a divisor in h, n is not primitive
else
}
if (t != 0) // this 'if' is merged with the for below in golfed code
{
// try all the sums, use a bit mask to find combinations
for(i = 1; t != 0 && i < 1<<l; i++)
{
t = n; // start with n and subtract, if ok result will be 0
m = 0.5; // start with mask 1/2 (nice that in Javascript we can mix int and floats)
r.forEach( v=> i & (m+=m) ? t -= v : 0);
}
if (t == 0 && n > 1) h[n] = 1; // add n to the hashmap (the value can be anything)
}
}
// the hashmap keys list is the result
return '' + Object.keys(h) // convert to string, adding commas
}

(test=()=> O.textContent=f(+I.value))();
<input id=I type=number oninput="test()" value=999><pre id=O></pre>

• @JörgHülsermann done, thanks for noticing – edc65 May 25 '17 at 19:21

# PHP, 263 Bytes

function m($a,$n){for($t=1,$b=2**count($a);--$b*$t;$t*=$r!=$n,$r=0)foreach($a as$k=>$v)$r+=($b>>$k&1)*$v;return$t;}for($o=[];$i++<$argn;m($d,$i)?:$o=array_merge($o,range($r[]=$i,3*$argn,$i)))for($d=[],$n=$i;--$n*!in_array($i,$o);)$i%$n?:$d[]=$n;echo join(",",$r);  Try it online! Expanded function m($a,$n){ for($t=1,$b=2**count($a);--$b*$t;$t*=$r!=$n,$r=0) #loop through bitmasks
foreach($a as$k=>$v)$r+=($b>>$k&1)*$v; # loop through divisor array return$t;} # returns false for semiperfect numbers
for($o=[];$i++<$argn; m($d,$i)? :$o=array_merge($o,range($r[]=$i,3*$argn,$i))) # Make the result array and the array of multiples of the result array for($d=[],$n=$i;--$n*!in_array($i,$o);) # check if integer is not in multiples array$i%$n?:$d[]=$n; # make divisor array echo join(",",$r); #Output


# CJam, 54 bytes

This solution feels a bit awkward, but since there have been few answers, and none in CJam, I thought I'd post it anyway:

Lli),2>{_N,1>{N\%!},_@&!\_,2,m*\f{.*:+}N#)e&{N+}&}fNS*


A good part of the increment over the posted Pyth solution comes from the fact that, as far as I could find, CJam does not have an operator to enumerate all subsets of a set. So it took some work to complete that with available operators. Of course, if there actually is a simple operator I missed, I'll look kind of silly. :)

Explanation:

L     Start stack with empty list that will become list of solutions.
li    Get input N and convert to int.
),2>  Build list of candidate solutions [2 .. N].
{     Start for loop over all candidate solutions.
_     Copy list of previous solutions, needed later to check for candidate being primitive.
N,1>  Build list of possible divisors [1 .. N-1].
{N\%!},  Filter list to only contain actual divisors of N.
_     Check if one of divisors is a previous solution. Start by copying divisor list.
@     Pull copy of list with previous solutions to top of stack
&!    Intersect the two lists, and check the result for empty. Will be used later.
_,    Get length of divisor list.
2,    Put [0 1] on top of stack.
m*    Cartesian power. Creates all 0/1 sequences with same length as divisor list.
\     Swap with divisor list.
f{.*:+}  Calculate element by element product of all 0/1 sequences with divisors,
and sum up the values (i.e. dot products of 0/1 sequences with divisors).
The result is an array with all possible divisor sums.
N#)  Find N in list of divisor sums, and covert to truth value.
e&   Logical and with earlier result from primitive test.
{N+}&  Add N to list of solutions if result is true.
}fN  Phew! We finally made it to the end of the for loop, and have a list of solutions.
S*   Join the list of solutions with spaces in between.


Try it online

# Julia, 161 149 bytes

n->(S(m)=!isempty(filter(i->i==unique(i)&&length(i)>1&&all(j->m%j<1,i),partitions(m)));for i=2:n S(i)&&!any(S,filter(k->i%k<1,1:i-1))&&println(i)end)


This creates an unnamed function that accepts an integer as input and prints the numbers to STDOUT separated by a newline. To call it, give it a name, e.g. f=n->....

Ungolfed + explanation:

# Define a function that determines whether the input is semiperfect
# (In the submission, this is defined as a named inline function within the
# primary function. I've separated it here for clarity.)

function S(m)
# Get all integer arrays which sum to m
p = partitions(m)

# Filter the partitions to subsets of the divisors of m
d = filter(i -> i == unique(i) && length(i) > 1 && all(j -> m % j == 0, i), p)

# If d is nonempty, the input is semiperfect
!isempty(d)
end

# The main function

function f(n)
# Loop through all integers from 2 to n
for i = 2:n
# Determine whether i is semiperfect
if S(i)
# If no divisors of i are semiperfect, print i
!any(S, filter(k -> i % k == 0, 1:i-1) && println(i)
end
end
end


Examples:

julia> f(5)

julia> f(40)
6
20
28