Sum of two squares and a perfect power

  1. Alpertron
  2. Programs
  3. Sum of two squares and a perfect power
Actions
Functions

This Web application finds the decomposition of any integer number into a sum of two squares and a cube, fifth power or seventh power.

Method

Let r be the exponent of the third number: 3, 5 or 7, and n be the number to be decomposed.

  • Step 1: Compute the first potential value of c as the rth root rounded down to an integer.
  • Step 2: Let d be the difference between the original number and the rth power of c. The number d is non-negative.
  • Step 3: Try to decompose d as a sum of two squares.
    • Step 3.1: If d equals zero, the output is 0 = 02 + 02 and go to step 5.
    • Step 3.2: Compute p and q such that d = p × 4q, where p is not multiple of 4.
    • Step 3.3: If the remainder of the division of p by 8 is not equal to 1, 2 or 5, the number d cannot be expressed as a sum of two squares, so subtract 1 from c and go back to step 2.
    • Step 3.4: Perform trial division to find small prime factors of d. The upper bound in this program is 32767.
    • Step 3.5: If there is a prime factor of the form 4k + 3 and its multiplicity is odd, d cannot be a sum of two squares, so subtract 1 from c and go back to step 2.
    • Step 3.6: If the cofactor is not a probable prime, we cannot determine whether d can be a sum of two squares, so subtract 1 from c and go back to step 2.
    • Step 3.7: Use the methods for two squares found in the page Every positive integer is a sum of four integer squares to find d = a2 + b2.
  • Step 4: Multiply both variables a and b by 2q.
  • Step 5: Show the decomposition as n = a2 + b2 + ck.

Expressions

You can enter numbers or numeric expressions in the input box including parentheses. The operations supported are:

  • + for addition
  • - for subtraction
  • * for multiplication
  • / for integer division
  • % for modulus (remainder of the integer division)
  • ^ or ** for exponentiation (the exponent must be greater than or equal to zero).
  • <, ==, >; <=, >=, != for comparisons. The operators return zero for false and -1 for true.
  • Ans: retrieves the last answer.
  • AND, OR, XOR, NOT for binary logic. The operations are done in binary (base 2). Positive (negative) numbers are prepended with an infinite number of bits set to zero (one).
  • SHL or <<: When b ≥ 0, a SHL b shifts a left the number of bits specified by b. This is equivalent to a × 2b. Otherwise, a SHL b shifts a right the number of bits specified by −b. This is equivalent to floor(a / 2b). Example: 5 SHL 3 = 40.
  • SHR or >>: When b ≥ 0, a SHR b shifts a right the number of bits specified by b. This is equivalent to floor(a / 2b). Otherwise, a SHR b shifts a left the number of bits specified by −b. This is equivalent to a × 2b. Example: -19 SHR 2 = -5.
  • n!: factorial (n must be greater than or equal to zero). Example: 6! = 6 × 5 × 4 × 3 × 2 = 720.
  • n!! ... !: multiple factorial (n must be greater than or equal to zero). It is the product of n times nk times n2k ... (all numbers greater than zero) where k is the number of exclamation marks. Example: 7!! = 7 × 5 × 3 × 1 = 105.
  • p#: primorial (product of all primes less or equal than p). Example: 12# = 11 × 7 × 5 × 3 × 2 = 2310.
  • B(n): Previous probable prime before n. Example: B(24) = 23.
  • F(n): Fibonacci number Fn from the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. where each element equals the sum of the previous two members of the sequence. Example: F(7) = 13.
  • L(n): Lucas number Ln = Fn-1 + Fn+1
  • N(n): Next probable prime after n. Example: N(24) = 29.
  • P(n): Unrestricted Partition Number (number of decompositions of n into sums of integers without regard to order). Example: P(4) = 5 because the number 4 can be partitioned in 5 different ways: 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1.
  • Gcd(m,n, ...): Greatest common divisor of these integers. Example: GCD(12, 16) = 4.
  • Lcm(m,n, ...): Least common multiple of these integers. Example: LCM(12, 16, 24) = 48.
  • Modinv(m,n): inverse of m modulo n, only valid when m and n are coprime, meaning that they do not have common factors. Example: Modinv(3,7) = 5 because 3 × 5 ≡ 1 (mod 7)
  • Modpow(m,n,r): finds mn modulo r. Example: Modpow(3, 4, 7) = 4, because 34 ≡ 4 (mod 7).
  • Totient(n): finds the number of positive integers less than n which are relatively prime to n. Example: Totient(6) = 2 because 1 and 5 do not have common factors with 6.
  • Jacobi(m,n): obtains the Jacobi symbol of m and n. When the second argument is prime, the result is zero when m is multiple of n, it is one if there is a solution of x² ≡ m (mod n) and it is equal to −1 when the mentioned congruence has no solution.
  • Random(m,n): integer random number between m and n.
  • Abs(n): absolute value of n.
  • IsPrime(n): returns zero if n is not probable prime, -1 if it is. Example: IsPrime(5) = -1.
  • Sqrt(n): Integer part of the square root of the argument.
  • Iroot(n,r): Integer r-root of the first argument. Example: Iroot(8, 3) = 2.
  • NumDigits(n,r): Number of digits of n in base r. Example: NumDigits(13, 2) = 4 because 13 in binary (base 2) is expressed as 1101.
  • SumDigits(n,r): Sum of digits of n in base r. Example: SumDigits(213, 10) = 6 because the sum of the digits expressed in decimal is 2+1+3 = 6.
  • RevDigits(n,r): finds the value obtained by writing backwards the digits of n in base r. Example: RevDigits(213, 10) = 312.

You can use the prefix 0x for hexadecimal numbers, for example 0x38 is equal to 56.

Batch processing

Write an expression per line, then press the Sum if cubes button. The output will be placed in the lower pane.

Blank lines or comment lines (which start with a numeral '#' character) will be replicated on the lower pane.

Expression loop: with the following syntax you can factor or determine primality of several numbers typing only one line. You have to type four or five expressions separated by semicolons:

  • First expression: It must start with the string 'x=' and it sets the first value of x.
  • Second expression: It must start with the string 'x=' and it sets the next value of x.
  • Third expression: It holds the end expression condition. If it is equal to zero (meaning false) the loop finishes, otherwise the loop continues.
  • Fourth expression: It holds the expression to be expressed as a sum of two squares and a power.
  • Optional fifth expression: If this expression is different from zero (meaning true), the fourth expression is processed, and if is zero (meaning false), the fourth expression is ignored.

Except for the first expression, all other expressions must include the variable x and/or the counter c.

If the end expression is false after processing 1000 numbers, the Continue button will appear. Pressing this button will make the program to process the next 1000 numbers and so on.

Example 1: Find the decomposition in a sum of two squares and a cube of the numbers from 0 to 5000. The line to type is: x=0;x=x+1;x<=5000;x. The calculator will show the results in blocks of 1000 values. You will need to press the Continue button to get the next block.

Example 2: Find the decomposition in a sum of two squares and a cube of the first 100 numbers of the form prime minus one. The line to type is: x=3;x=n(x);c<=100;x-1.

Source code

You can download the source of the this program from GitHub. Notice that the source code is in C language and you need the Emscripten environment in order to generate JavaScript.

Written by Dario Alpern. Last updated 4 December 2022.