Talk:Primes - allocate descendants to their ancestors

Task comments

Hi, on reading the task I thought that:

1. The language examples show no output.
2. If they did show output, would it be too long?
3. The task shows time comparisons which is difficult to make comparable.
4. The task shows time comparisons between different languages - we normally write tasks in which solutions only need authors to use one language.
5. The task mentions comparing algorithms but does not explain the different algorithms in pseudocode or a textual description.

--Paddy3118 (talk) 17:16, 24 February 2015 (UTC)

Hi,

1. 'The list layout' showed a partial ouput for parent [46]. I've changed it to the full results for parent [46].
2. Yes, the output is too big to be posted (5.079 KB), that's why, I give the total of all descendants.
3. I did put some time comparisons, because I was so surprised, from a few seconds in C to almost 10 minutes required by the "Visual Basic .NET with collection". This is my first 'Visual Basic .NET' program, I probably did something wrong, because the program runs in 20 seconds, now. I deleted the time comparisons.
4. I didn't know one author/one language. Where can I find the rules ?
5. I already put a textual description : "This solution could be compared to the solution that would use the decomposition into primes for all the numbers between 5 and 3^33".

--Old man (talk) 09:00, 25 February 2015 (UTC)

Task is ambiguous

I would like to see some ambiguities resolved, here:

(1) Timing. Timing is meaningless because of potential differences between machines. (Imagine I use elastic map reduce here, for example.) See also Rosetta_Code:Village_Pump/Run_times_on_examples?

(2) Inadequate illustration: So, ok, an ancestor is the sum of the factors of a prime. But the example only considers a case where there are two factors. What are the ancestors of 72? When we are summing ancestors, if a number is an ancestor of two other numbers do we count it once or twice? And so on...

(3) Inadequate definition: What is a descendant? Clearly there are some bounds on descendants from the problem writeup stating that 46 has 557 descendants, but what are they?

Hypothetically, this part of the "C implementation" might define the bounds of the problem:

<lang C>#define MAXPRIME 99 // greatest prime factor

1. define MAXPARENT 99 // greatest parent number
2. define NBRPRIMES 30 // max number of prime factors
3. define NBRANCESTORS 10 // max number of parent's ancestors</lang>

But there might be additional constraints implemented in the algorithm and/or data structures. This kind of thing really belongs in the task description.

Hypothetically, I might try inspecting some of the code samples, to see how they behave. But, for example, the C implementation does not compile. Among its problems is that it tries to do malloc(sizeof(Children)) when what has been defined is struct Children.

(I am rather reluctant to attempt to debug someone else's buggy code to attempt to reverse engineer the bounds of the problem when I could more easily ask for those bounds.)

So... would it be possible to rephrase the task to address these issues? --Rdm (talk) 02:53, 26 February 2015 (UTC)

Hi, too.

(1) Timing. I already addressed this question, yesterday. See my answer to Paddy3118, point 3, above.

(2) I posted "... is to add the decomposition into prime factors of a number to get its 'ancestors'".

What difference does it make if there are more than 2 prime factors ?

I also gave the example of 3^33 = 5.559.060.566.555.523 (parent 99).

That is, 3^33 --> 3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3 = 99

The ancestor lists has to be provided for a delimited set of ancestors (from 5 to 99), see the task description.

And, yes, some ancestors may have common ancestors.

(3) If 25 is the Parent of 46, you can deduct that 46 is a descendant (child) of 25.

And I posted : "... use the decomposition into primes for all the numbers between 5 and 3^33".

The 557 descendants of the ancestor 46 are posted, since yesterday, see my answer to Paddy3118, point 1, above.

MAXPARENT is clearly stated in the task description (ancestors from 5 to 99).

MAXPRIME is also clearly stated in the task description "You only have to consider the prime factors < 100".

This information could also have been deducted from MAXPARENT.

And, yes, 99 is not a prime factor. MAXPRIME is given as an upper bound.

MAXPRIME is used to get a list of all the prime factors which are lower than (or equal to) MAXPRIME.

NBRPRIMES and NBRANCESTORS are only used to delimit the size of 2 tables. They are not relevant to solve the problem.

malloc(sizeof(Children))

Thanks, for this information, it's a typo, my compiler didn't even warn me on that. I changed the C code.

malloc(sizeof(struct Children))

I posted one solution, there are maybe hundreds.

Hope it helps!

--Old man (talk) 10:39, 26 February 2015 (UTC)

This does help. And it looks like you are counting the number of distinct numbers as opposed to how many times a number occurs.

That said, there's something very quirky about "for a delimited set of ancestors (from 5 to 99)" - you are clearly considering ancestors smaller than 5. All of your examples include such ancestors. By reading your code, I can see what you are doing - but that doesn't make for a good task description (and leads to all sorts of unreasonable hypothesis about what you might be doing, such as those I was considering when I asked my initial set of questions).

I would highly recommend that you drop the lower limit on ancestors to 2 (because 2 is a relevant ancestor, given the results you are getting) and fix your code so it doesn't crash when you do that. --Rdm (talk) 14:38, 26 February 2015 (UTC)

Read the task description, again. All the necessary information are stated in the description. Some information are clearly stated, some others are somehow hidden (i.e. a prime factor is not its own ancestor nor its own descendant). Also, the title clearly states "allocate descendants to their ancestors", that is, each descendant is counted for 1. 46 is a descendant of 25, but 46 is also the ancestor of 129. Is this a reason to exclude 46 from the descendants of 25 ? Of course not.

Where ? Give me an example, because there is no ancestor smaller than 5. 5 has no ancestor and 1, 2, 3 and 4 do not have any ancestor nor descendant.

I think, you are out of context, I posted a task, but, I do not impose a solution.

2 is not a relevant ancestor, because 2 is not a ancestor at all. But, if you want to consider 2, 3 and 4 as ancestors, you are free to post an alternate task.

--Old man (talk) 08:30, 2 March 2015 (UTC)

I think that the hidden information should not be hidden. Perhaps it is sufficient for the hidden information to be stated on the discussion page, but this hidden information is not information that I get from reading the task description in its current form.

For example, I feel it's not clear what you mean by 'the title clearly states "allocate descendants to their ancestors", that is, each descendant is counted for 1" -- for one what?

Still, after studying the output from your C program, I see that each descendant is counted once for each ancestor that it is a descendant of. For example, 20 is a descendant of 8 and it is also a descendant of 9, so it gets counted twice when both 8 and 9 are considered as parents. So if I set MAXPRIME and MAXPARENT to 11, in your C program, it's rather clear that 20 would be counted for 2 (as opposed to being counted as 20 in the total, for example).

Of course, I understand that can not be what you meant. But without considerable effort spent on your code, and some time in this discussion, I would not know what you had meant. It's worth spending some time addressing the ambiguities of interpretation which necessarily arise from the use of the english language (or any language which humans have developed for speaking with each other - but in this case we are using english). There are good biological reasons for these ambiguities, and it's relatively simple to address them.

Another difficulty is that in your implementation, for example, 8 is an ancestor of 26, but 26 is not a descendant of 8. Why is the reason for this not stated in the task description? --Rdm (talk) 15:56, 2 March 2015 (UTC)