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]

• ror3d: @Zgarb if you allow for a chain of 0 divisor twists, then how is not every number a descendant of any other number?
• Zgarb: @rcrmn To me, a chain of zero operations means the identity operation. So allowing zero divisor twists only implies that every number is a descendant of itself.
• ror3d: @Zgarb okay, so the definition should be changed to express that, because if not, as far as I can tell, any number is considered a descendant of every other number. I don't know why it's needed the reflexivity. Would you care to explain?
• Zgarb: @rcrmn I changed the wording slightly, is it clearer now?
• ror3d: @Zgarb sorry but no, it's not an operation, you are defining a relationship between numbers. If you define the relationship < for the natural numbers, for every n you get every number smaller than it but not itself. I think this should be something similar. This way I think only 4 would be its own descendant (not sure about that, though).

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

• Alex A.: I'm no Python expert, but is there a reason why you need set() in there? Can't you just return the sorted list?
• Sp3000: @Alex set() is to remove duplicates :)
• Alex A.: Oh, okay. Neat. Nice work!
• xnor: Can you perhaps do [n]+sum(...,[]) as sum(...,[n])?
• Sp3000: @xnor Ah yes, I can. I've never used anything but [] as a base case for summing lists, so I completely forgot!

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).

• Geobits: Welcome to PPCG! You can save a couple by changing a*b to n on line 9.
• TNT: Thanks for the welcome and the suggestion! Yeah, it'll take a while for me to spot these small things. Every byte counts! Thanks again!
• Geobits: You can also save two more by putting c=n+a-b inside add(). Alternatively, you could get rid of c altogether and just use n+a-b in both places for those same two bytes.
• TNT: Speaking of which, I don't think I need to use add twice. Hold on a moment...
• Geobits: But the second loop isn't needed on the whole. If you have an a that you know divides n cleanly, then you shouldn't loop to find b, it's just n/a. At that point it starts getting closer and closer to mine ;)

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

• Alex A.: It's my understanding that Octave can end blocks with just end rather than endfor and endfunction. That would save you 11 bytes.
• dcsohl: Hey, you are right! Not how I learned the language and never realized it could be done. Why are you the first one to point this out after I've done multiple golfs with it?
• Alex A.: I only knew that because I recently looked it up after seeing it in someone else's golf on another question. I've never used Octave and it's been years since I've used Matlab. My guess is that there aren't all that many active Octave users on PPCG, but I could be wrong.
• Alex A.: My pleasure, glad I could help. Nice solution.

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#_24ドル*f-&:mq:if-~}%|}*$p

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