Reciprocal Of Reciprocals

Relevant wiki: General Diophantine Equations - Problem Solving

First, $N = a\|b = \frac 1 {1/a+1/b} = \frac{ab}{a+b}.$ This is an integer if $a+b$ divides $ab$ . Now if $a$ and $b$ are coprime, this immediately implies that $a+b|a$ and $a+b|b$ ; but that means $a = b = 0$ , so that doesn't work.

Assume therefore that $a$ and $b$ have a common divisor: $d = \text{gcd}(a, b)$ , and $a = da'$ , $b = db'$ , with coprime $a'$ and $b'$ . Then $N = \frac{da'db'}{da'+db'} = \frac{da'b'}{a'+b'}.$ The condition $a'+b'|da'b'$ now leads to $a' + b'|d$ , so that $d = n(a'+b')$ for some integer $n$ , and $a = n(a'+b')a',\ \ b = n(a'+b')b',\ \ N = na'b'.$ Since $a', n\geq 1$ , it is easy to see that $b = n(a'+b')b' > (b')^2$ so that $b \leq 100$ implies $b' < 10$ . The rest we check by hand:

• $(a',b') = (1,2)$ : 16 solutions $3\|6 = 2$ and multiples (namely, $3n\|6n = 2n$ for $n = 1,\dots,16$ ).

• $(a',b') = (1,3)$ : 8 solutions $4\|12 = 3$ and multiples (namely, $4n\|12n = 3n$ for $n = 1,\dots,8$ ).

• $(a',b') = (2,3)$ : 6 solutions $10\|15 = 6$ and multiples (...).

• $(a',b') = (1,4)$ : 5 solutions $5\|20 = 4$ and multiples.

• $(a',b') = (3,4)$ : 3 solutions $21\|28 = 12$ and multiples.

• $(a',b') = (1,5)$ : 3 solutions $6\|30 = 5$ and multiples.

• $(a',b') = (2,5)$ : 2 solutions $14\|35 = 10;\ 28\|70 = 20$ .

• $(a',b') = (3,5)$ : 2 solutions $24\|40 = 15;\ 48\|80 = 30$ .

• $(a',b') = (4,5)$ : 2 solutions $36\|45 = 5;\ 72\|90 = 10$ .

• $(a',b') = (1,6)$ : 2 solutions $7\|42 = 6;\ 14\|84 = 12$ .

• $(a',b') = (5,6)$ : 1 solution $55\|66 = 30$ .

• $(a',b') = (1,7)$ : 1 solution $8\|56 = 7$ .

• $(a',b') = (2,7)$ : 1 solution $18\|63 = 14$ .

• $(a',b') = (3,7)$ : 1 solution $30\|70 = 21$ .

• $(a',b') = (4,7)$ : 1 solution $44\|77 = 28$ .

• $(a',b') = (5,7)$ : 1 solution $60\|84 = 35$ .

• $(a',b') = (6,7)$ : 1 solution $78\|91 = 42$ .

• $(a',b') = (1,8)$ : 1 solution $9\|72 = 8$ .

• $(a',b') = (3,8)$ : 1 solution $33\|88 = 24$ .

• $(a',b') = (1,9)$ : 1 solution $10\|90 = 9$ .

• $(a',b') = (2,9)$ : 1 solution $22\|99 = 18$ .

Adding them all, we find $\boxed{60}$ solutions.

First, simplify the fraction to $\frac{ab}{a+b}$ .

Let $(a, b) = d, a = a_1*d, b = b_1*d$ . Then, the fraction simplifies to $\frac{da_1b_1}{a_1+b_1}$ . Observe that $(a_1 + b_1, a_1) = (b_1, a_1) = 1$ , and similarly $(a_1+b_1,b_1) = 1$ . Thus, in order for this fraction to be an integer, $a_1+b_1 = 1$ or $a_1+b_1 | d$ . Clearly $a_1+b_1 \neq 1$ , so we must have $a_1+b_1 | d$ .

All we have to do is count such $a_1, b_1, d$ , because a triple of these values always maps to distinct $a,b$ . Let $d = (a_1+b_1)*x$ , for some integer $x$ . We have that $100 \geq b = db_1 = xb_1(a_1+b_1) > b_1^2$ . Thus, $10 > b_1$ , and checking the remaining cases by hand yields $\boxed{60}$ .

(Let $b_1 = 9, 8, 7,\ldots, 2$ and do casework on the value of $x$ ).

Code uploaded online

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <iostream.h>
int main ()
{
    int count =0;
    for (int k=1; k<=100; k++)
    {
          for (int j=k; j<=100; j++)
          {
                if (( j*k % (j+k) == 0) && j!=k)  count++;
          }
    }
cout<<count;
return 0;
}

Here's some GNU assembly code that does the job. Fortunately, the number of pairs is less than 255, so instead of making an itoa function, I just packed it into the exit code. The ELF is only 1064 bytes, and doesn't make memory accesses for data.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// Compiles with `gcc -nostdlib <assembly file>`
#define SYS_EXIT    $60

#define LIMIT       $100

.global _start
.text

_start:
    /* Entry Point: */
    xorb    %bl, %bl
    xorw    %si, %si        // Counter
    incb    %bl             // a=1
loopa:
    movb    %bl, %cl
    cmpb    LIMIT-1, %bl
    jg      exit                // if a>99, done.

    loopb:
        incb    %cl            // b = a+1
        cmpb    LIMIT, %cl 
        jg      doneb           // if b>100, done.

        movb    %cl, %al
        mulb    %bl                  // ax = b*a
        movb    %cl, %bh
        addb    %bl, %bh             // bh = a+b
        divb    %bh

        cmpb    $0, %ah
        jne     loopb               // if (ba)%(a+b) != 0, don't count
        incw    %si             // count otherwise.
        jmp     loopb

    doneb:
        incb    %bl
        jmp     loopa

exit:
    movq    SYS_EXIT, %rax
    movzxw   %si, %rdi   // The exit code.
    syscall

You can try it out yourself (on an x64 Linux machine). Save the above as "recipOfRecip.sx". Example of a test:

1
2
3
4
5

$ gcc -nostdlib recipOfRecip.sx
$ ./a.out; echo $?
60
$ ls -l a.out | awk '{print $5;}'    # print size
1064