2
$\begingroup$

We have three positive integers numbers $a,$ $b$ and $c$ (they have no common divisor), which satisfy $b^2 + c^2 = a^2.$ If $s \le 12$ is the sum of the digits of $a,$ $b$ and $c,$ I have to calculate $a,$ $b$ and $c.$ First, $a,$ $b$ and $c$ form a primitive Pythagorean triple, that means $(a,b,c) = (m^2 + n^2,2mn,m^2-n^2),$ with $m>n$. Then I found some informations about the digits sum: A digit sum $s_b (n) $ is a sum of the base-$b$ digits of $n$. The digit sum of a given integer is the sum of all its digits (e.g. the digit sum of $84001$ is calculated as $8+1+0+0+1=13$). Digit sums are most often computed using the decimal representation of the given number, but they may be calculated in any other base. Different bases give different digit sums, with the digit sums for binary being on average smaller than those for any other base. The digit sum of a number $x$ in base $b$ is given by: $$\sum_{n=0}^{⌊\log_b⁡x ⌋} \frac {1}{b^n} [x(\mod b^{n+1}) – x(\mod b^n)].$$ The digits sum $s_b (n) $ satisfies the congruence $n ≡ s_b (n) (\mod ⁡b-1) $.

In base $10$, this congruence is the basis of casting out nines and of fast divisibility tests such as those for $3$ and $9$. The digits sum $s_b (n) $ satisfies the following unexpected identity $$\sum_{n=1}^{\infty} \frac { s_b (n) }{ n(n+1)} = \frac {b}{b-1} \ln b.$$

We define $f(d,n) $ to be the number of integers of up to $d$ decimal digits with digit sum less than or equal to $n$. It can be seen that this function is given by the formula

$$f(d,n)=\sum_{i=0}^d(-1)^i\binom{d}i\binom{n+d-10i}d\;.$$

How can I use the above formulas? Thank you

$\endgroup$
  • $\begingroup$ Not all of this is relevant. You only need to be concerned with the sum of the decimal digits. The first thing to do is to cut out the immaterial parts, and focus on what's relevant. By the way, have you found any solutions yet? (Hint:There's one obvious one.) $\endgroup$ – saulspatz Apr 30 '18 at 17:38
  • $\begingroup$ I have a particular solution, for example $(3,4,5),$ but I've lost a general method counting $a,b,c$ $\endgroup$ – Steven Apr 30 '18 at 17:41
  • $\begingroup$ $(5,12,13)$ also works. I'd be (somewhat) surprised if there are any others but don't see a proof. $\endgroup$ – lulu Apr 30 '18 at 18:12
  • $\begingroup$ Yes, this seems like a hard problem. What is the source of this problem, may I ask? $\endgroup$ – saulspatz Apr 30 '18 at 18:16
  • $\begingroup$ Are we considering only $s=12$ or $s \le 12$ $\endgroup$ – qwr Apr 30 '18 at 18:50
2
$\begingroup$

This is only a start, not a complete solution, but it's way too long for a comment. I'm still working on this, and I hope that others will provide suggestions, or perhaps be able to extend these ideas into a solution.

First, you omitted a couple of facts about the $m$ and $n$ that generate primitive Pythagorean triples. ("Primitive" means that $a,b,c$ are pairwise relatively prime.) First, $m,n$ must be coprime. Second one must be even, and one must be odd. Note that the second fact implies that $c$ is odd.

The important fact about the digit sum of a number is congruent to the original number, modulo $9.$ (This is the basis of "casting out nines.") So we know that $$a+b+c\equiv3\pmod9$$ So far I'm only considering the $s=12$ case. That's really just because of confusion on my part, but I'm sure we can rule out some of the smaller values based on size considerations like those below.

I used these facts to write a little python script to compute the possible values of $(a,b,c)\pmod9.$

for a in range(9):
    for b in range(a,9):        
        for c in range(9):
            if (c*c-a*a-b*b)%9 == 0 and (a+b+c)%9==3:
                if a%3==0 and b%3==0: continue
                print(a,b,c)

This produced the output

1 3 8
2 3 7
3 4 5
3 5 4
3 7 2
3 8 1

Note that each line represents two possibilities. For example the first line represents both

$$a\equiv1\pmod9,b\equiv3\pmod9,c\equiv8\pmod9$$ and $$a\equiv3\pmod9,b\equiv1\pmod9,c\equiv8\pmod9$$

Consider the last line, where $c\equiv1\pmod9$ The digit sum of $c$ must be either $1$ or $10$ since we know it's $\le12$. If it is $1$, then $c=10^n$ for some $n>1$ which is impossible, since $c$ is odd. On the other hand, if the digit sum is $10$, then both $a$ and $b$ are powers of $10$ so not relatively prime. (We know that $1$ is not a member of any Pythagorean triple.)

Therefore, we can eliminate the last possibility. In the other cases, considerations of size lead to the conclusion that the numbers shown are the actual digit sums, not merely the congruence classes.

So far, I haven't been able to rule out any additional lines, nor to see how to find the general solution for lines that can't be ruled out.

EDIT

I updated my python script to consider $s<12$. I also included the facts that the digit sum can never be $0$ and in the case of $c$ it can't be $1$ as shown above. Here's the new script:

for s in range(13):
    for a in range(1,9):
        for b in range(a,9): 
            if a%3==0 and b%3==0: continue
            for c in range(2,9):
                if (c*c-a*a-b*b)%9 == 0 and a+b+c==s:
                    print(a,b,c)

This produced the output:

2 3 2
2 6 2
3 4 4
1 3 8
2 3 7
3 4 5
3 5 4
3 7 2

EDIT

I tried out the suggestion of qwr, namely looking at the last two digits of $a,b,c$. Taking $a$ to be even and $b$ to be odd leaves me $62$ possibilities. I think I see how to eliminate a number of them, but it doesn't look very promising overall.

$\endgroup$
  • $\begingroup$ you can extend this to the digit sum directly and considering $a,b,c \mod 100$ instead of $\mod 9$. This will rule out a lot of cases $\endgroup$ – qwr Apr 30 '18 at 19:04
  • $\begingroup$ @ qwr You mean I should consider the sum of the squares of the last two digits? That's an idea. $\endgroup$ – saulspatz Apr 30 '18 at 19:23
  • $\begingroup$ yes there are not that many pairs for $a,b,c$ that could work since $s \le 12$ is actually quite small $\endgroup$ – qwr Apr 30 '18 at 19:26
  • $\begingroup$ Are you sure 62? that seems like a lot $\endgroup$ – qwr May 1 '18 at 16:59
  • $\begingroup$ @qwr Well, 62 is what I got. I'm not saying that can't be trimmed, but the small values are a real problem. For example $a,b,c=0,1,1$. We can say $a=100A, b= 100B+1, c=100C+1$ and then get an equation in $A,B,C$ where the sum of the digits has to be $\le 10$ but that's a long row to hoe, especially with so many cases. I think it requires a better idea. I'm thinking about using congruences mod $81$ instead of $100.$ That might be easier to relate to what we know mod $9$. $\endgroup$ – saulspatz May 1 '18 at 17:10
1
$\begingroup$

Here I present ideas and empirical results I listed in the comments of saulspatz's answer. (Not a full solution)

Let $d(n)$ be the digit sum function. I consider the last 3 digits of $a,b,c$, calling these $a',b',c'$, such that $d(a')+d(b')+d(c') \le 12$.

However, if $a'^2 + b'^2 \ne c'^2$, then I require $d(a') + d(b') + d(c') \le 11$, since then we need additional digits beyond the last 3. I also make the assumption that $a' \ne 0$ though I don't have a proof of this.

def digit_sum(x):
    return sum(map(int, str(x)))

S_LIM = 12

sol_count = 0
for a in range(1, 1000):
    da = digit_sum(a)
    for b in range(a, 1000):
        db = digit_sum(b)
        if da + db > S_LIM: continue

        for c in range(1, 1000, 2):
            dc = digit_sum(c)

            if da + db + dc <= S_LIM and \
                (a**2 + b**2) % 1000 == (c**2) % 1000:
                if a**2 + b**2 != c**2 and da + db + dc > S_LIM-1: 
                    continue

                sol_count += 1
                print("{:03} {:03} {:03} {}".format(a, b, c, da+db+dc))

print("Solutions:", sol_count)

Note that $(3,4,5), (5,12,13), (21,220,221)$ are the only solutions with $a,b,c \le 1000$.

001 020 201 6
001 020 701 11
001 032 005 11
001 040 051 11
001 040 301 9
001 060 301 11
001 100 001 3
001 100 251 10
001 100 501 8
001 120 201 7
001 140 301 10
001 200 001 4
001 200 251 11
001 200 501 9
001 220 201 8
001 240 301 11
001 300 001 5
001 300 501 10
001 320 201 9
001 400 001 6
001 400 501 11
001 420 201 10
001 500 001 7
001 520 201 11
001 600 001 8
001 700 001 9
001 800 001 10
001 900 001 11
003 004 005 12
003 040 103 11
003 100 003 7
003 200 003 8
003 300 003 9
003 400 003 10
003 500 003 11
005 012 013 12
005 100 005 11
011 020 211 8
011 040 311 11
011 100 011 5
011 100 511 10
011 120 211 9
011 200 011 6
011 200 511 11
011 220 211 10
011 300 011 7
011 320 211 11
011 400 011 8
011 500 011 9
011 600 011 10
011 700 011 11
013 100 013 9
013 200 013 10
013 300 013 11
020 021 221 10
020 051 001 9
020 061 011 11
020 101 051 10
020 101 301 8
020 103 003 9
020 111 311 10
020 113 013 11
020 151 101 11
020 201 401 10
020 203 103 11
020 301 001 7
020 311 011 9
020 321 021 11
020 401 101 9
020 411 111 11
020 501 201 11
021 100 021 7
021 120 221 11
021 200 021 8
021 220 221 12
021 300 021 9
021 400 021 10
021 500 021 11
023 100 023 11
031 100 031 9
031 200 031 10
031 300 031 11
040 101 401 11
040 201 001 8
040 211 011 10
040 301 101 10
041 100 041 11
051 100 301 11
051 120 001 10
051 220 001 11
060 201 001 10
100 101 101 5
100 101 601 10
100 103 103 9
100 111 111 7
100 113 113 11
100 121 121 9
100 131 131 11
100 201 201 7
100 203 203 11
100 211 211 9
100 221 221 11
100 251 001 10
100 301 051 11
100 301 301 9
100 311 311 11
100 401 401 11
100 501 001 8
100 511 011 10
100 601 101 10
101 120 051 11
101 120 301 9
101 200 101 6
101 200 601 11
101 220 301 10
101 300 101 7
101 320 301 11
101 400 101 8
101 500 101 9
101 600 101 10
101 700 101 11
103 120 003 10
103 200 103 10
103 220 003 11
103 300 103 11
111 120 311 11
111 200 111 8
111 300 111 9
111 400 111 10
111 500 111 11
120 201 401 11
120 301 001 8
120 311 011 10
120 401 101 10
121 200 121 10
121 300 121 11
140 201 001 9
140 211 011 11
140 301 101 11
160 201 001 11
200 201 201 8
200 211 211 10
200 251 001 11
200 301 301 10
200 501 001 9
200 511 011 11
200 601 101 11
201 240 001 10
201 300 201 9
201 340 001 11
201 400 201 10
201 500 201 11
211 300 211 11
220 301 001 9
220 311 011 11
220 401 101 11
300 301 301 11
300 501 001 10
301 320 001 10
301 420 001 11
400 501 001 11
Solutions: 161
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.