greedy computation of pseudoperfect numbers?

[Maximilian Hasler]

> For both sorts of pseudoperfect numbers, allowing divisor one A005835,
>  and forbidding divisor one A136446, a greedy method _seems_ to always
>  work for deciding whther a given n in in the sequence:


You may have noticed that the algorithm I posted some days ago
(included again at the end of the mail ; the copy to seqfan was
rejected since I used a bad From: address, but you should have got it
directly)
* on one hand, IS quite fast (a(1..1000) in .3 sec on a laptop,
 without any optimization (e.g. the recursion could easily be replaced
by a loop)
* on the other hand, TRIES to do it the greedy way (starting with
largest values),
 but in case of negative response, gives another try without the
largest divisor.
* shows you, if you add to the last line (when greedy fails)
 a corresponding print() command (e.g.(...) & !print("failed for "n)),
 for which values it does not work the greedy  way.

Maximilian

%o A005835 (PARI)
isA005835(n, d=0)={ local(t);
 /* Return nonzero iff n is the sum of a subset of d which defaults to
the set of proper divisors of n */
 if( !d, /* Initialize d */ d=vecextract(divisors(n), "^-1")
 ,/*else check if n equals to one element of d */ setsearch( Set(d), n
) & return(1));
 /* Remove terms > n */ while( #d>1 & d[ #d]>n, d=vecextract(d, "^-1"));
 /* If n is not smaller than the sum of all terms, we're done */ n >=
(t = sum(i=1, #d, d[i])) & return( n==t );
 /* If n is larger than M=max(d), then try to write n-M in terms of d \ { M } */
 n > d[#d] & isA005835( n - d[#d], vecextract( d, "^-1") ) & return(1);
 /* else only d \ {M} is needed */ isA005835( n, vecextract( d, "^-1" ))}



Joerg said:

I was just too sure no odd n would turn up.

allowing divisor one, greedy gives these odd n<10000:
945, 1575, 2205, 2835, 3465, 4725, 5355, 5985, 6435, 6615, 6825, 7245,
7425, 7875, 8085, 8415, 8505, 8925, 9135, 9765,

forbidding divisor one, greedy gives:
1575, 2835, 3465, 6435, 6615, 7245, 7425, 7875, 8085, 8415, 8505,
8925, 9135, 9765,

>From the webpage:
"the only odd obundant numbers for which the greedy
4095 5775 9555 12915 21945 22275 24255 27405 29925 35805 38745

(note all divisible by 5.)
It is not said whether these are pseudoperfect.

All in all an interesting but apparently hard problem.


Are any of these sequences sufficiently well-defined
to be included in the OEIS?
Neil