Official Everybody Edits Forums

1. If n is your number, the answer is σ(n/v(n))-1 where σ(n) is the divisor function which gives the number of divisors of n and v(n) is the greatest power of two dividing n. For example, 115 = 5x23 gives σ(115)=4 (v(n)=1) so the answer is 3, like Koya found.

This is equivalent to finding when n is a difference of two non consecutive triangular numbers. These are of the form 1/2(i)(i+1), so we want to solve for i>j

2n=i^2+i-j^2-j = (i-j)(j+i+1)

One of these factors is odd, while the other is even. In fact, for any pair of factors (a,b) with opposite parities we can solve for i,j. So we're really interested in the number of distinct factor pairs (a,b) with opposite parities of 2n. WLOG, let a be the even one: then a=2*v(n)*(odd number), while b is another odd number. Therefore it's only dependent on the odd numbers, which gives σ(n/v(n)) ways. Subtract one for the case of just 'n' as our list of numbers.

2. See later post.

3. This is best done with modular arithmetic. Let a>b with gcd(a,b)=1, since if gcd(a,b)>1 then we can't make numbers not divisible by their gcd. Once we have achieved all possible residues modulo b using only multiples of a, we know that we can create any number after the greatest multiple.Given that a,b are relatively prime, a modulo b is relatively prime to b and so a*(b-1) will cover the last residue modulo b. However, we can create b-1 numbers before a*(b-1) using previously obtained residues, so we really can obtain every value that is at last (a-1)*(b-1).

4. (I'm taking this to mean find the set of numbers with x divisors) This actually relates a bit back to the first one: we want to find the set S_x of all n such that σ(n)=x. First, make a list of all ways to get a product of x with integers>1. If the prime factorization of n is n = p_1^e_1 * p_2^e_2 ... , then σ(n)=(e_1+1)(e_2+1)... . For each way to express x, we subtract 1 from each term in the product to get the e_i. Then substitute any set of primes in to get a value for n.

As an example: take x=4. We have 4=2x2, 4 (only ways), so S_x=p_1*p_2 or p_1^3.

5. No. In the end, we want 4^n = 1 (mod 3) squares. However, at every step there are 0 mod 3 squares.

6. We get a cycle when we hit a number which is equal to the sum of the cubes of its digits. However, we can easily put a bound on this: there are floor(log(n)) digits (base 10 log here), each which is at most 9^3. When 9^3ceil(log(n))<n, we can't have such a number anymore. This happens around n=3000. (Although they become increasingly improbable way before this)

A quick brute force search gives 1, 153, 370, 371, 407 as the only such numbers. For the next bit, let f(n) be the sum of the cubes of the digits of n.

The specific fixed point is dependent on the starting number modulo 3: a number is a multiple of 3 plus k if the sum its digits is a multiple of 3 plus k, and cubing preserves values of numbers modulo 3, so repeated application of f on some number n does not change its value modulo 3. if 3|n, then f(n) 153. If n is a multiple of 3 plus one, it goes to 1 or 370 if there isn't a cycle. If n is a multiple of 3 plus two, it goes to 371 or 407. These aren't too tricky to prove, since f(n)<n for n>3000, so we only need to check that all n in this range end up in a cycle or a fixed point as claimed. It does turn out that all multiples of 3 end up at 153, and all multiples of 3 plus two end up at 371 or 407. Unfortunately, this fails for multiples of 3 plus one because you can end up in a cycle with a number like 133.

I really liked this last one, I had no clue that there was any sort of pattern in this sort of stuff. 3000 numbers isn't a lot to search, but if anybody can lower the number of checks you make or eliminate them completely that would be nice.