﻿ Sum of four squares

Sum of squares

1. Alpertron
2. Web applications
3. Sum of four squares
Actions
Functions

This Web application finds the decomposition of any natural number up to 10000 digits into up to four squares.

Notice that it does not find the prime factorization of the number entered by the user, so some cases where two squares would be enough, it will be represented as a sum of three squares. For example, 10000998089 = 95317² + 30260².

Read the methods used in this applet.

Expressions

You can also enter expressions that use the following operators and parentheses:

• - 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.
• SHL or <<: Shift left the number of bits specified on the right operand.
• SHR or >>: Shift right the number of bits specified on the right operand.
• n!: factorial (n must be greater than or equal to zero).
• 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).
• B(n): Previous probable prime before n
• F(n): Fibonacci number Fn
• L(n): Lucas number Ln = Fn-1 + Fn+1
• N(n): Next probable prime after n
• P(n): Unrestricted Partition Number (number of decompositions of n into sums of integers without regard to order).
• 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.
• FloorDiv(m,n): integer part of the quotient of m divided by n. Examples: floordiv(10, 7) = 1 and floordiv(-10, 7) = -2.
• Mod(m,n): value of m modulo the absolute value of n. Examples: Mod(10, 7) = 3 and Mod(-10, 7) = 4.
• Modinv(m,n): inverse of m modulo n, only valid when gcd(m,n)=1.
• Modpow(m,n,r): finds mn modulo r.
• 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.
• Sign(n): returns zero if n is zero, −1 if negative or 1 if positive.
• IsPrime(n): returns zero if n is not probable prime, −1 if it is.
• 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.
• SumDigits(n,r): Sum of digits of n in base r.
• RevDigits(n,r): finds the value obtained by writing backwards the digits of n in base r.

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

Configuration

You can change settings for this application by pressing the Config button when a factorization is not in progress. A new window will pop up where you can select different settings:

• Digits per group: In order to improve readability, big numbers are separated by spaces forming groups of a fixed number of digits. With this input box, you can determine the number of digits in a group.
• Hexadecimal output: If this checkbox is set, the numbers are shown in hexadecimal format instead of decimal, which is the common notation. To enter numbers in hexadecimal format, you will need to precede them by the string 0x. For instance, 0x38 = 56. The program shows hexadecimal numbers with monospaced font.
• Keyboard: This enables the user to select between numeric or complete (alphanumeric) virtual keyboard. The virtual keyboard appears on the screen when the user selects an input box on touch screens.

The configuration is saved in your device, so when you start again the calculator, all settings remain the same.

Batch processing

Write an expression per line, then press the Sum if squares 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 decompose several numbers in a sum of squares 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 squares.
• 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 sum of squares 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 sum of squares 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 quote is represented by a percent sign followed by a quote.

Example 3: For each number between 0 and 100, show whether the number is prime and then the decomposition in squares both in decimal and hexadecimal.

The line to write is: x=0; x=x+1; x<=100; "%d is prime: %l, %Fd, %Fx":x:isprime(x):x:x

Source code

You can download the source of the current program and the old sum of four squares applet 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 9 June 2024.