Problem 388

[tpgettys]

From the origin O(0,0,0) all lines are drawn to the other lattice points.
Let D(N) be the number of distinct such lines.

What is meant by "distinct"? I presume it means lines with different "slopes", but two overlapping line segments with different end-points could certainly be considered distinct.

[LarryBlake]

It says lines, not segments. Only 1 line goes through 0,0,0 and 1,1,1. The same line also goes through 2,2,2.

[Grigorenko]

For example, if D(10^10)=111111111............222222222, then is correct answer 111111111222222222 ? Thank you.

[Marcus_Andrews]

Yes, that's correct. The answer is 18 digits long (no spaces). It's just the first 9 digits immediately followed by the last 9 digits.

For example, if D(10^10)=111111111............222222222, then is correct answer 111111111222222222 ? Thank you.

[EKG]

To clarify the problem would D(1) = 7 or something else?

[thundre]

To clarify the problem would D(1) = 7 or something else?

I guess it's OK to answer since they gave D(1000000) in the problem.

Yes, D(1) = 7.

[janardhanan]

Someone please confirm this.
D(100) = 850957

Just want to make sure whether I am going in right direction or not

[EKG]

So I've been thinking about this problem for a couple of days now. Solutions that I've come up with would definitely cause me to run out of memory and/or not finish in my lifetime. Even an O(n) algorithm that goes from 0 to 10¹⁰ would be pretty expensive in terms of time. From looking at the problem it seems to be related to composite numbers and GCDs. However, my basic knowledge in number theory will not do very well in terms helping me to find a solution for the problem. Could anyone point out some specific areas of number theory that would be worth looking into? Perhaps a simpler problem that this one builds on?

Thanks,

EKG

[hk]

I think you can answer this question by yourself.
Hint: GCD is sometimes called HCF.
Which problem(s) you solved mention(s) that term?
(No need to answer here.)
(A more explicit hint: the problem I have in mind has a nice PDF with a sublinear algoritm that many solvers of this problem used.
There is little needed to adapt the algoritm from that PDF to this problem.
I looked it up and you've solved that one indeed.
)

[EKG]

Thanks hk! Will look into it!

[snapey1979]

Thanks for the hint hk. I have an algorithm which does 10^6 in half a second and gets to 10^8 before it gives up. I think I know the problem you have in mind, so I'll go and have a look and see if I can expand mine.

[browni3141]

I had the same problem as the OP. I think that the words "from" and "to" imply endpoints (at least for me they did). Also, something else seems weird about the wording, but I can't put my finger on it.