Find primitive semiperfect numbers
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.
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
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
l = r.push(i); // add divisor to r and adjust l
}
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>