A027424 annoys me. I keep thinking there must be a fast way to compute this sequence, but I can't find it. Another way to state my frustration: What is A027424(10^9)?
A027424 annoys me.
Yes, I agree. For the record, the sort-of complementary problem is A033677: Smallest divisor of n >= sqrt(n). Then A033677(n) is the smallest k such that n appears in the k-by-k multiplication table, and A027424(k) is the number of n with A033677(n) <= k. These seq's should probably be cross-linked to each other. I agree with Rich that maybe the first differences seem easier to attack, but this might be deceptive... this is asking how many of {n,2n,3n,...,n^2} are not ij for i,j<n, and doing this based on the factorization of n means recognizing things like "No, 34*16 isn't new for n=34, because it already appeared as 32*17." Maybe for each n you can look at its prime factorization and calculate one list of likely factor swaps to look out for? Ugh. --Michael Kleber kleber@brandeis.edu
A similar problem is A018805, where a(n) is the number of coprime pairs (x, y) with 1 <= x,y <= n. I found the recursion a(n) = n^2 - SUM(j=2..n; a(floor(n/j))) This recusion is gotten by noticing that the number of pairs (x,y) with gcd(x,y) = j, 1 <= x,y <= n, is just a(floor(n/j)). So a(n) is gotten by taking all n^2 pairs, and subtracting out those whose gcd's fall between 2 and n. With clever programming, this identity is the basis for a fairly quick algorithm for a(n), much faster than the obvious SUM(j=1..n; phi(j)). I was hoping something similar might be done with A027424. For example, observe that the number of distinct even entries in the n x n multiplication table is just the number of distinct entries in the n x floor(n/2) multiplication table, analogously for entries divisible by other primes.
A033677 is the smallest divisor of n >= sqrt(n). The Maple program given for this looks quite inefficient. It appears to obtain the divisors of n, then compare them all to the sqrt(n). A033677(n) will be the central element or larger of two central elements of the sorted list of divisors of n. You do not need to compute sqrt(n) to obtain this value. ----- Original Message ----- From: Michael Kleber To: math-fun Sent: Saturday, July 05, 2003 10:46 PM Subject: Re: [math-fun] Annoyed
A027424 annoys me.
Yes, I agree. For the record, the sort-of complementary problem is A033677: Smallest divisor of n >= sqrt(n). Then A033677(n) is the smallest k such that n appears in the k-by-k multiplication table, and A027424(k) is the number of n with A033677(n) <= k. These seq's should probably be cross-linked to each other. I agree with Rich that maybe the first differences seem easier to attack, but this might be deceptive... this is asking how many of {n,2n,3n,...,n^2} are not ij for i,j<n, and doing this based on the factorization of n means recognizing things like "No, 34*16 isn't new for n=34, because it already appeared as 32*17." Maybe for each n you can look at its prime factorization and calculate one list of likely factor swaps to look out for? Ugh. --Michael Kleber kleber@brandeis.edu _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sunday, July 6, 2003, at 03:18 am, David Wilson wrote:
A033677 is the smallest divisor of n >= sqrt(n). The Maple program given for this looks quite inefficient. It appears to obtain the divisors of n, then compare them all to the sqrt(n). A033677(n) will be the central element or larger of two central elements of the sorted list of divisors of n.
Yes, or the minimal divisor d such that n/d <= d. (But I don't see any way to use it to help answer the original question.) I've been contemplating the infinite rectangular array of which A027424 is the main diagonal: the (m,n) entry is the number of distinct products ij with 1<=i<=m, i<=j<=n: 1 2 3 4 5 6 7 8 9 10 2 3 5 6 8 9 11 12 14 15 3 5 6 8 11 12 15 17 18 20 4 6 8 9 13 15 19 20 22 24 5 8 11 13 14 17 22 24 27 28 6 9 12 15 17 18 24 27 30 32 7 11 15 19 22 24 25 29 33 36 8 12 17 20 24 27 29 30 35 39 9 14 18 22 27 30 33 35 36 41 10 15 20 24 28 32 36 39 41 42 Couldn't get a recursion for this one either thought... --Michael Kleber kleber@brandeis.edu
I think computing the partial sums is slower than just plain counting the distinct elements of the table... :-(. ----- Original Message ----- From: Michael Kleber To: math-fun Sent: Saturday, July 05, 2003 10:46 PM Subject: Re: [math-fun] Annoyed
A027424 annoys me.
I agree with Rich that maybe the first differences seem easier to attack, but this might be deceptive... this is asking how many of {n,2n,3n,...,n^2} are not ij for i,j<n, and doing this based on the factorization of n means recognizing things like "No, 34*16 isn't new for n=34, because it already appeared as 32*17." Maybe for each n you can look at its prime factorization and calculate one list of likely factor swaps to look out for? Ugh. --Michael Kleber kleber@brandeis.edu
participants (2)
-
David Wilson -
Michael Kleber