13
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ @Zgarb if you allow for a chain of 0 divisor twists, then how is not every number a descendant of any other number? \$\endgroup\$ – rorlork Feb 18 '15 at 15:54
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Zgarb Feb 18 '15 at 15:59
  • \$\begingroup\$ @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? \$\endgroup\$ – rorlork Feb 18 '15 at 16:03
  • \$\begingroup\$ @rcrmn I changed the wording slightly, is it clearer now? \$\endgroup\$ – Zgarb Feb 18 '15 at 16:07
  • \$\begingroup\$ @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). \$\endgroup\$ – rorlork Feb 18 '15 at 16:20
9
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I'm no Python expert, but is there a reason why you need set() in there? Can't you just return the sorted list? \$\endgroup\$ – Alex A. Feb 18 '15 at 20:41
  • \$\begingroup\$ @Alex set() is to remove duplicates :) \$\endgroup\$ – Sp3000 Feb 18 '15 at 21:34
  • \$\begingroup\$ Oh, okay. Neat. Nice work! \$\endgroup\$ – Alex A. Feb 18 '15 at 21:57
  • \$\begingroup\$ Can you perhaps do [n]+sum(...,[]) as sum(...,[n])? \$\endgroup\$ – xnor Feb 23 '15 at 7:02
  • \$\begingroup\$ @xnor Ah yes, I can. I've never used anything but [] as a base case for summing lists, so I completely forgot! \$\endgroup\$ – Sp3000 Feb 23 '15 at 10:28
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! You can save a couple by changing a*b to n on line 9. \$\endgroup\$ – Geobits Feb 18 '15 at 20:12
  • \$\begingroup\$ 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! \$\endgroup\$ – TNT Feb 18 '15 at 20:21
  • \$\begingroup\$ 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. \$\endgroup\$ – Geobits Feb 18 '15 at 20:24
  • \$\begingroup\$ Speaking of which, I don't think I need to use add twice. Hold on a moment... \$\endgroup\$ – TNT Feb 18 '15 at 20:25
  • \$\begingroup\$ 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 ;) \$\endgroup\$ – Geobits Feb 18 '15 at 20:30
4
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ It's my understanding that Octave can end blocks with just end rather than endfor and endfunction. That would save you 11 bytes. \$\endgroup\$ – Alex A. Feb 18 '15 at 21:10
  • \$\begingroup\$ 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? \$\endgroup\$ – dcsohl Feb 19 '15 at 16:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Alex A. Feb 19 '15 at 17:53
  • \$\begingroup\$ Well, thank you for pointing it out. \$\endgroup\$ – dcsohl Feb 19 '15 at 18:11
  • \$\begingroup\$ My pleasure, glad I could help. Nice solution. \$\endgroup\$ – Alex A. Feb 19 '15 at 18:16
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.