Sum of two squares and a perfect power
- Alpertron
- Web applications
- Sum of two squares and a perfect power
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 = 0^{2} + 0^{2} and go to step 5.
- Step 3.2: Compute p and q such that d = p × 4^{q}, 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 = a^{2} + b^{2}.
- Step 4: Multiply both variables a and b by 2^{q}.
- Step 5: Show the decomposition as n = a^{2} + b^{2} + c^{k}.
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 × 2^{b}. Otherwise, a SHL b shifts a right the number of bits specified by −b. This is equivalent to floor(a / 2^{−b}). 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 / 2^{b}). Otherwise, a SHR b shifts a left the number of bits specified by −b. This is equivalent to a × 2^{−b}. 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 n − k times n − 2k ... (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 F_{n} 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 L_{n} = F_{n-1} + F_{n+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 m^{n} modulo r. Example: Modpow(3, 4, 7) = 4, because 3^{4} ≡ 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 one of the sum of powers 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 decompose several numbers in a sum of powers by 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
.
The fourth expression can be changed to a format string and several expressions. The format string indicates what is displayed. Inside this string you can specify conversion clauses that start by a percent sign and they are case insensitive:
- %D: show expression as a decimal number.
- %X: show expression as a hexadecimal number.
- %L: show yes if the expression is not zero and no if it is zero.
- %FD: decompose expression as a sum of powers decimal number.
- %FX: show expression as a hexadecimal number.
The expressions are written after the string, separated by colons. There must be a colon also between the string and the first expression.
To print a percent sign, you have to write two percent signs, and a quotation mark is represented by a percent sign followed by a quotation mark.
Example 3: For each number between -100 and 100, show whether the number is prime and then the decomposition in two squares and a cube both in decimal and hexadecimal.
The line to write is: x=-100; x=x+1; <=100; "%d is prime: %l, %Fd, %Fx":x:isprime(x):x:x
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 3 August 2023.