[seqfan] Re: Who understands Granville numbers?

[hv at crypt.org]

Alonso Del Arte <alonso.delarte at gmail.com> wrote:
:So I come across the concept of Granville numbers
:(A118372<http://www.research.att.com/~njas/sequences/A118372>)
:in Jean-Marie de Koninck's book *Those Fascinating Numbers*. But the concept
:is giving me a headache. Is the definition of the set S recursive (one
:having to do a complete divisor tree to figure out membership) or am I
:completely misunderstanding it? I've had an easier time doing my taxes.

The comment on A118372 says:
  S={1}. Assume n>1 and that all numbers m<n have already been tested.
  Let s=sum{d: d|n, d<n and d in S}. If s<=n then n is now in S.

I take that to mean:
  S_0 = {1}.
  s_n = sum{ d: d | n & d < n & d in S_{n-1} }
  S_n := { S_{n-1}        s_n > n
         { S_{n-1} U {n}  s_n <= n

The Maple program seems to confirm that with the statement:
  if s <= n then S := S union {n} fi;

Hugo