Iterated Divisor Twist

Question

Definitions

Let m and n be positive integers. We say that m is a divisor twist of n if there exists integers 1 < a ≤ b such that n = a*b and m = (a - 1)*(b + 1) + 1. If m can be obtained from n by applying zero or more divisor twists to it, then m is a descendant of n. Note that every number is its own descendant.

For example, consider n = 16. We can choose a = 2 and b = 8, since 2*8 = 16. Then

(a - 1)*(b + 1) + 1 = 1*9 + 1 = 10

which shows that 10 is a divisor twist of 16. With a = 2 and b = 5, we then see that 7 is a divisor twist of 10. Thus 7 is a descendant of 16.

The task

Given a positive integer n, compute the descendants of n, listed in increasing order, without duplicates.

Rules

You are not allowed to use built-in operations that compute the divisors of a number.

Both full programs and functions are accepted, and returning a collection datatype (like a set of some kind) is allowed, as long as it is sorted and duplicate-free. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

1 ->  [1]
2 ->  [2] (any prime number returns just itself)
4 ->  [4]
16 -> [7, 10, 16]
28 -> [7, 10, 16, 25, 28]
51 -> [37, 51]
60 -> [7, 10, 11, 13, 15, 16, 17, 18, 23, 25, 28, 29, 30, 32, 43, 46, 49, 53, 55, 56, 60]

Answer 1

Python 2, 109 98 85 82 bytes

f=lambda n:sorted(set(sum(map(f,{n-x+n/x for x in range(2,n)if(n<x*x)>n%x}),[n])))

Since (a-1)*(b+1)+1 == a*b-(b-a) and b >= a, descendants are always less than or equal to the original number. So we can just start with the initial number and keep generating strictly smaller descendants until there are none left.

The condition (n<x*x)>n%x checks two things in one - that n<x*x and n%x == 0.

(Thanks to @xnor for taking 3 bytes off the base case)

Pyth, 32 bytes

LS{s+]]bmydm+-bk/bkf><b*TT%bTr2b

Direct translation of the above, except for the fact that Pyth seems to choke when trying to sum (s) on an empty list.

This defines a function y which can be called by appending y<number> at the end, like so (try it online):

LS{s+]]bmydm+-bk/bkf><b*TT%bTr2by60

CJam, 47 45 bytes

{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}

Also using the same method, with a few modifications. I wanted to try CJam for comparison, but unfortunately I'm much worse at CJam than I am at Pyth/Python, so there's probably a lot of room for improvement.

The above is a block (basically CJam's version of unnamed functions) that takes in an int and returns a list. You can test it like so (try it online):

{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}:G; 60 Gp

Answer 2

Java, 148 146 104 bytes

Golfed version:

import java.util.*;Set s=new TreeSet();void f(int n){s.add(n);for(int a=1;++a*a<n;)if(n%a<1)f(n+a-n/a);}

Long version:

import java.util.*;
Set s = new TreeSet();
void f(int n) {
    s.add(n);
    for (int a = 1; ++a*a < n;)
        if (n%a < 1)
            f(n + a - n/a);
}

So I'm making my debut on PPCG with this program, which uses a TreeSet (which automatically sorts the numbers, thankfully) and recursion similar to Geobits' program, but in a different manner, checking for multiples of n and then using them in the next function. I'd say this is a pretty fair score for a first-timer (especially with Java, which doesn't seem to be the most ideal language for this kind of thing, and Geobits' help).

Answer 3

Java, 157 121

Here's a recursive function that gets descendants of each descendant of n. It returns a TreeSet, which is sorted by default.

import java.util.*;Set t(int n){Set o=new TreeSet();for(int i=1;++i*i<n;)o.addAll(n%i<1?t(n+i-n/i):o);o.add(n);return o;}

With some line breaks:

import java.util.*;
Set t(int n){
    Set o=new TreeSet();
    for(int i=1;++i*i<n;)
        o.addAll(n%i<1?t(n+i-n/i):o);
    o.add(n);
    return o;
}

Answer 4

Octave, 107 96

function r=d(n)r=[n];a=find(!mod(n,2:sqrt(n-1)))+1;for(m=(a+n-n./a))r=unique([d(m) r]);end;end

Pretty-print:

function r=d(n)
  r=[n];                          # include N in our list
  a=find(!mod(n,2:sqrt(n-1)))+1;  # gets a list of factors of a, up to (not including) sqrt(N)
  for(m=(a+n-n./a))               # each element of m is a twist
    r=unique([d(m) r]);           # recurse, sort, and find unique values
  end;
end

Answer 5

Haskell, 102 100 bytes

import Data.List
d[]=[]
d(h:t)=h:d(t++[a*b-b+a|b<-[2..h],a<-[2..b],a*b==h])
p n=sort$nub$take n$d[n]

Usage: p 16 which outputs [7,10,16]

The function d recursively calculates all descendants, but does not check for duplicates, so many appear more than once, e. g. d [4] returns an infinite list of 4s. The functions p takes the first n elements from this list, removes duplicates and sorts the list. Voilà.

Answer 6

CJam - 36

ri_a\{_{:N,2>{NNImd!\I-z*-}fI}%|}*$p

Try it online

Or, different method:

ri_a\{_{_,2f#_2$4*f-&:mq:if-~}%|}*$p

I wrote them almost 2 days ago, got stuck at 36, got frustrated and went to sleep without posting.