Arithmetic derivative
The arithmetic derivative of an integer (more specifically, the Lagarias arithmetic derivative) is a function defined for integers, based on prime factorization, by analogy with the product rule for the derivative of a function that is used in mathematical analysis. Accordingly, for natural numbers n, the arithmetic derivative D(n) is defined as follows:
You are encouraged to solve this task according to the task description, using any language you may know.
- D(0) = D(1) = 0.
- D(p) = 1 for any prime p.
- D(mn) = D(m)n + mD(n) for any m,n ∈ N. (Leibniz rule for derivatives).
Additionally, for negative integers the arithmetic derivative may be defined as -D(-n) (n < 0).
- Examples
D(2) = 1 and D(3) = 1 (both are prime) so if mn = 2 * 3, D(6) = (1)(3) + (1)(2) = 5.
D(9) = D(3)(3) + D(3)(3) = 6
D(27) = D(3)*9 + D(9)*3 = 9 + 18 = 27
D(30) = D(5)(6) + D(6)(5) = 6 + 5 * 5 = 31.
- Task
Find and show the arithmetic derivatives for -99 through 100.
- Stretch task
Find (the arithmetic derivative of 10^m) then divided by 7, where m is from 1 to 20.
- See also
ALGOL 68
BEGIN PROC lagarias = (LONG INT n) LONG INT: # Lagarias arithmetic derivative #
IF n < 0
THEN -lagarias (-n)
ELIF n = 0 OR n = 1
THEN 0
ELIF PROC small pf = (LONG INT j, k) LONG INT: # Smallest prime factor #
(j %* k = 0 | k | small pf (j, k + 1));
LONG INT f = small pf (n, 2); LONG INT q = n % f;
q = 1
THEN 1
ELSE q * lagarias (f) + f * lagarias (q)
FI;
FOR n FROM -99 TO 100
DO print (("D(", whole (n, 0), ") = ", whole (lagarias (n), 0), new line))
OD;
new line (standout);
FOR n TO 20
DO LONG INT m = LONG 10 ^ n;
print (("D(", whole (m, 0), ") / 7 = ", whole (lagarias (m) % 7, 0), new line))
OD
END- Output:
D(-99) = -75 D(-98) = -77 D(-97) = -1 D(-96) = -272 ... D(96) = 272 D(97) = 1 D(98) = 77 D(99) = 75 D(100) = 140 D(10) / 7 = 1 D(100) / 7 = 20 D(1000) / 7 = 300 ... D(1000000000000000000) / 7 = 1800000000000000000 D(10000000000000000000) / 7 = 19000000000000000000 D(100000000000000000000) / 7 = 200000000000000000000
ALGOL W
begin
integer procedure lagarias ( integer value n ) ; % Lagarias arithmetic derivative %
if n < 0
then -lagarias (-n)
else if n = 0 or n = 1
then 0
else begin
integer f, q;
integer procedure smallPf ( integer value j, k ) ; % Smallest prime factor %
if j rem k = 0 then k else smallPf (j, k + 1);
f := smallPf (n, 2); q := n div f;
if q = 1
then 1
else q * lagarias (f) + f * lagarias (q)
end lagarias ;
for n := -99 until 100 do begin
writeon( i_w := 6, s_w := 0, " ", lagarias (n) );
if n rem 10 = 0 then write()
end for_n
end.- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
C
#include <stdio.h>
#include <stdint.h>
typedef uint64_t u64;
void primeFactors(u64 n, u64 *factors, int *length) {
if (n < 2) return;
int count = 0;
int inc[8] = {4, 2, 4, 2, 4, 6, 2, 6};
while (!(n%2)) {
factors[count++] = 2;
n /= 2;
}
while (!(n%3)) {
factors[count++] = 3;
n /= 3;
}
while (!(n%5)) {
factors[count++] = 5;
n /= 5;
}
for (u64 k = 7, i = 0; k*k <= n; ) {
if (!(n%k)) {
factors[count++] = k;
n /= k;
} else {
k += inc[i];
i = (i + 1) % 8;
}
}
if (n > 1) {
factors[count++] = n;
}
*length = count;
}
double D(double n) {
if (n < 0) return -D(-n);
if (n < 2) return 0;
int i, length;
double d;
u64 f[80], g;
if (n < 1e19) {
primeFactors((u64)n, f, &length);
} else {
g = (u64)(n / 100);
primeFactors(g, f, &length);
f[length+1] = f[length] = 2;
f[length+3] = f[length+2] = 5;
length += 4;
}
if (length == 1) return 1;
if (length == 2) return (double)(f[0] + f[1]);
d = n / (double)f[0];
return D(d) * (double)f[0] + d;
}
int main() {
u64 ad[200];
int n, m;
double pow;
for (n = -99; n < 101; ++n) {
ad[n+99] = (int)D((double)n);
}
for (n = 0; n < 200; ++n) {
printf("%4ld ", ad[n]);
if (!((n+1)%10)) printf("\n");
}
printf("\n");
pow = 1;
for (m = 1; m < 21; ++m) {
pow *= 10;
printf("D(10^%-2d) / 7 = %.0f\n", m, D(pow)/7);
}
return 0;
}
- Output:
As Go example
C++
#include <iomanip>
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
template <typename IntegerType>
IntegerType arithmetic_derivative(IntegerType n) {
bool negative = n < 0;
if (negative)
n = -n;
if (n < 2)
return 0;
IntegerType sum = 0, count = 0, m = n;
while ((m & 1) == 0) {
m >>= 1;
count += n;
}
if (count > 0)
sum += count / 2;
for (IntegerType p = 3, sq = 9; sq <= m; p += 2) {
count = 0;
while (m % p == 0) {
m /= p;
count += n;
}
if (count > 0)
sum += count / p;
sq += (p + 1) << 2;
}
if (m > 1)
sum += n / m;
if (negative)
sum = -sum;
return sum;
}
int main() {
using boost::multiprecision::int128_t;
for (int n = -99, i = 0; n <= 100; ++n, ++i) {
std::cout << std::setw(4) << arithmetic_derivative(n)
<< ((i + 1) % 10 == 0 ? '\n' : ' ');
}
int128_t p = 10;
std::cout << '\n';
for (int i = 0; i < 20; ++i, p *= 10) {
std::cout << "D(10^" << std::setw(2) << i + 1
<< ") / 7 = " << arithmetic_derivative(p) / 7 << '\n';
}
}
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^ 1) / 7 = 1 D(10^ 2) / 7 = 20 D(10^ 3) / 7 = 300 D(10^ 4) / 7 = 4000 D(10^ 5) / 7 = 50000 D(10^ 6) / 7 = 600000 D(10^ 7) / 7 = 7000000 D(10^ 8) / 7 = 80000000 D(10^ 9) / 7 = 900000000 D(10^10) / 7 = 10000000000 D(10^11) / 7 = 110000000000 D(10^12) / 7 = 1200000000000 D(10^13) / 7 = 13000000000000 D(10^14) / 7 = 140000000000000 D(10^15) / 7 = 1500000000000000 D(10^16) / 7 = 16000000000000000 D(10^17) / 7 = 170000000000000000 D(10^18) / 7 = 1800000000000000000 D(10^19) / 7 = 19000000000000000000 D(10^20) / 7 = 200000000000000000000
EasyLang
func lagarias n .
if n < 0
return -lagarias -n
.
if n = 0 or n = 1
return 0
.
f = 2
while n mod f <> 0
f += 1
.
q = n / f
if q = 1
return 1
.
return q * lagarias f + f * lagarias q
.
for n = -99 to 100
write lagarias n & " "
.Factor
USING: combinators formatting grouping io kernel math
math.primes.factors prettyprint ranges sequences ;
: n' ( m -- n )
{
{ [ dup neg? ] [ neg n' neg ] }
{ [ dup 2 < ] [ drop 0 ] }
{ [ factors dup length 1 = ] [ drop 1 ] }
[ unclip-slice swap product 2dup n' * spin n' * + ]
} cond ;
-99 100 [a..b] [ n' ] map 10 group
[ [ "%5d" printf ] each nl ] each
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
Go
Using float64 (finessed a little) to avoid the unpleasantness of math/big for the stretch goal. Assumes that int type is 64 bit.
package main
import (
"fmt"
"rcu"
)
func D(n float64) float64 {
if n < 0 {
return -D(-n)
}
if n < 2 {
return 0
}
var f []int
if n < 1e19 {
f = rcu.PrimeFactors(int(n))
} else {
g := int(n / 100)
f = rcu.PrimeFactors(g)
f = append(f, []int{2, 2, 5, 5}...)
}
c := len(f)
if c == 1 {
return 1
}
if c == 2 {
return float64(f[0] + f[1])
}
d := n / float64(f[0])
return D(d)*float64(f[0]) + d
}
func main() {
ad := make([]int, 200)
for n := -99; n < 101; n++ {
ad[n+99] = int(D(float64(n)))
}
rcu.PrintTable(ad, 10, 4, false)
fmt.Println()
pow := 1.0
for m := 1; m < 21; m++ {
pow *= 10
fmt.Printf("D(10^%-2d) / 7 = %.0f\n", m, D(pow)/7)
}
}
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^1 ) / 7 = 1 D(10^2 ) / 7 = 20 D(10^3 ) / 7 = 300 D(10^4 ) / 7 = 4000 D(10^5 ) / 7 = 50000 D(10^6 ) / 7 = 600000 D(10^7 ) / 7 = 7000000 D(10^8 ) / 7 = 80000000 D(10^9 ) / 7 = 900000000 D(10^10) / 7 = 10000000000 D(10^11) / 7 = 110000000000 D(10^12) / 7 = 1200000000000 D(10^13) / 7 = 13000000000000 D(10^14) / 7 = 140000000000000 D(10^15) / 7 = 1500000000000000 D(10^16) / 7 = 16000000000000000 D(10^17) / 7 = 170000000000000000 D(10^18) / 7 = 1800000000000000000 D(10^19) / 7 = 19000000000000000000 D(10^20) / 7 = 200000000000000000000
Haskell
import Control.Monad (forM_)
import Data.List (intercalate)
import Data.List.Split (chunksOf)
import Math.NumberTheory.Primes (factorise, unPrime)
import Text.Printf (printf)
-- The arithmetic derivative of a number, which is assumed to be non-negative.
arithderiv_ :: Integer -> Integer
arithderiv_ 0 = 0
arithderiv_ n = foldr step 0 $ factorise n
where step (p, v) s = s + n `quot` unPrime p * fromIntegral v
-- The arithmetic derivative of any integer.
arithderiv :: Integer -> Integer
arithderiv n | n < 0 = negate $ arithderiv_ (negate n)
| otherwise = arithderiv_ n
printTable :: [Integer] -> IO ()
printTable = putStrLn
. intercalate "\n"
. map unwords
. chunksOf 10
. map (printf "%5d")
main :: IO ()
main = do
printTable [arithderiv n | n <- [-99..100]]
putStrLn ""
forM_ [1..20 :: Integer] $ \i ->
let q = 7
n = arithderiv (10^i) `quot` q
in printf "D(10^%-2d) / %d = %d\n" i q n
- Output:
$ arithderiv
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
D(10^1 ) / 7 = 1
D(10^2 ) / 7 = 20
D(10^3 ) / 7 = 300
D(10^4 ) / 7 = 4000
D(10^5 ) / 7 = 50000
D(10^6 ) / 7 = 600000
D(10^7 ) / 7 = 7000000
D(10^8 ) / 7 = 80000000
D(10^9 ) / 7 = 900000000
D(10^10) / 7 = 10000000000
D(10^11) / 7 = 110000000000
D(10^12) / 7 = 1200000000000
D(10^13) / 7 = 13000000000000
D(10^14) / 7 = 140000000000000
D(10^15) / 7 = 1500000000000000
D(10^16) / 7 = 16000000000000000
D(10^17) / 7 = 170000000000000000
D(10^18) / 7 = 1800000000000000000
D(10^19) / 7 = 19000000000000000000
D(10^20) / 7 = 200000000000000000000
J
Implementation:
D=: {{ +/y%q:1>.|y }}"0
In other words: find the sum of the argument divided by each of the sequence of prime factors of its absolute value (with a special case for zero -- we use the maximum of either 1 or that absolute value when finding the sequence of prime factors).
Task example:
D _99+i.20 10
_75 _77 _1 _272 _24 _49 _34 _96 _20 _123
_1 _140 _32 _45 _22 _124 _1 _43 _108 _176
_1 _71 _18 _80 _55 _39 _1 _156 _1 _59
_26 _72 _1 _61 _18 _192 _51 _33 _1 _92
_1 _31 _22 _92 _16 _81 _1 _56 _20 _45
_14 _112 _1 _25 _39 _48 _1 _41 _1 _68
_16 _21 _1 _60 _12 _19 _14 _80 _1 _31
_1 _32 _27 _15 _10 _44 _1 _13 _10 _24
_1 _21 _1 _32 _8 _9 _1 _16 _1 _7
_6 _12 _1 _5 _1 _4 _1 _1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
Also, it seems like it's worth verifying that order of evaluation does not create an ambiguity for the value of D (order shouldn't matter, since summation of integers is order independent):
15 10 6 + 2 3 5 * D 15 10 6
31 31 31
Stretch task:
(D 10x^1+i.4 5)%7
1 20 300 4000 50000
600000 7000000 80000000 900000000 10000000000
110000000000 1200000000000 13000000000000 140000000000000 1500000000000000
16000000000000000 170000000000000000 1800000000000000000 19000000000000000000 200000000000000000000
Java
import java.math.BigInteger;
public final class ArithmeticDerivative {
public static void main(String[] aArgs) {
System.out.println("Arithmetic derivatives for -99 to 100 inclusive:");
for ( int n = -99, column = 0; n <= 100; n++ ) {
System.out.print(String.format("%4d%s",
derivative(BigInteger.valueOf(n)), ( ++column % 10 == 0 ) ? "\n" : " "));
}
System.out.println();
final BigInteger seven = BigInteger.valueOf(7);
for ( int power = 1; power <= 20; power++ ) {
System.out.println(String.format("%s%2d%s%d",
"D(10^", power, ") / 7 = ", derivative(BigInteger.TEN.pow(power)).divide(seven)));
}
}
private static BigInteger derivative(BigInteger aNumber) {
if ( aNumber.signum() == -1 ) {
return derivative(aNumber.negate()).negate();
}
if ( aNumber == BigInteger.ZERO || aNumber == BigInteger.ONE ) {
return BigInteger.ZERO;
}
BigInteger divisor = BigInteger.TWO;
while ( divisor.multiply(divisor).compareTo(aNumber) <= 0 ) {
if ( aNumber.mod(divisor).signum() == 0 ) {
final BigInteger quotient = aNumber.divide(divisor);
return quotient.multiply(derivative(divisor)).add(divisor.multiply(derivative(quotient)));
}
divisor = divisor.add(BigInteger.ONE);
}
return BigInteger.ONE;
}
}
- Output:
Arithmetic derivatives for -99 to 100 inclusive: -75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 -1 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^ 1) / 7 = 1 D(10^ 2) / 7 = 20 D(10^ 3) / 7 = 300 D(10^ 4) / 7 = 4000 D(10^ 5) / 7 = 50000 D(10^ 6) / 7 = 600000 D(10^ 7) / 7 = 7000000 D(10^ 8) / 7 = 80000000 D(10^ 9) / 7 = 900000000 D(10^10) / 7 = 10000000000 D(10^11) / 7 = 110000000000 D(10^12) / 7 = 1200000000000 D(10^13) / 7 = 13000000000000 D(10^14) / 7 = 140000000000000 D(10^15) / 7 = 1500000000000000 D(10^16) / 7 = 16000000000000000 D(10^17) / 7 = 170000000000000000 D(10^18) / 7 = 1800000000000000000 D(10^19) / 7 = 19000000000000000000 D(10^20) / 7 = 200000000000000000000
jq
For this task, gojq (the Go implementation of jq) is used for numerical accuracy, though the C implementation has sufficient accuracy at least for D(10^16).
See Prime_decomposition#jq for the def of factors/0 used here.
To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
# In case gojq is used:
def _nwise($n):
def nw: if length <= $n then . else .[0:$n] , (.[$n:] | nw) end;
nw;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def D($n):
if $n < 0 then -D(- $n)
elif $n < 2 then 0
else [$n | factors] as $f
| ($f|length) as $c
| if $c <= 1 then 1
elif $c == 2 then $f[0] + $f[1]
else ($n / $f[0]) as $d
| D($d) * $f[0] + $d
end
end ;
def task:
def task1:
reduce range(-99; 101) as $n ([]; .[$n+99] = D($n))
| _nwise(10) | map(lpad(4)) | join(" ");
def task2:
range(1; 21) as $i
| "D(10^\($i)) / 7 = \( D(10|power($i))/7 )" ;
task1, "", task2 ;
task- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^1) / 7 = 1 D(10^2) / 7 = 20 D(10^3) / 7 = 300 D(10^4) / 7 = 4000 D(10^5) / 7 = 50000 D(10^6) / 7 = 600000 D(10^7) / 7 = 7000000 D(10^8) / 7 = 80000000 D(10^9) / 7 = 900000000 D(10^10) / 7 = 10000000000 D(10^11) / 7 = 110000000000 D(10^12) / 7 = 1200000000000 D(10^13) / 7 = 13000000000000 D(10^14) / 7 = 140000000000000 D(10^15) / 7 = 1500000000000000 D(10^16) / 7 = 16000000000000000 D(10^17) / 7 = 170000000000000000 D(10^18) / 7 = 1800000000000000000 D(10^19) / 7 = 19000000000000000000 D(10^20) / 7 = 200000000000000000000
Julia
using Primes
D(n) = n < 0 ? -D(-n) : n < 2 ? zero(n) : isprime(n) ? one(n) : typeof(n)(sum(e * n ÷ p for (p, e) in eachfactor(n)))
foreach(p -> print(lpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(map(D, -99:100)))
println()
for m in 1:20
println("D for 10^", rpad(m, 3), "divided by 7 is ", D(Int128(10)^m) ÷ 7)
end
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
D for 10^1 divided by 7 is 1
D for 10^2 divided by 7 is 20
D for 10^3 divided by 7 is 300
D for 10^4 divided by 7 is 4000
D for 10^5 divided by 7 is 50000
D for 10^6 divided by 7 is 600000
D for 10^7 divided by 7 is 7000000
D for 10^8 divided by 7 is 80000000
D for 10^9 divided by 7 is 900000000
D for 10^10 divided by 7 is 10000000000
D for 10^11 divided by 7 is 110000000000
D for 10^12 divided by 7 is 1200000000000
D for 10^13 divided by 7 is 13000000000000
D for 10^14 divided by 7 is 140000000000000
D for 10^15 divided by 7 is 1500000000000000
D for 10^16 divided by 7 is 16000000000000000
D for 10^17 divided by 7 is 170000000000000000
D for 10^18 divided by 7 is 1800000000000000000
D for 10^19 divided by 7 is 19000000000000000000
D for 10^20 divided by 7 is 200000000000000000000
Lua
Tested with Lua 5.1 (LuaJIT and OpenResty), 5.3.6 and 5.4.6.
Lua 5.2.4 didn't like the string.format. Also the format of the larger D values appears to be sensitive to the Lua version.
do local function lagarias (n) -- Lagarias arithmetic derivative
if n < 0
then return -lagarias (-n)
elseif n == 0 or n == 1
then return 0
else local function smallPf (j, k) -- Smallest prime factor
if j % k == 0 then return k else return smallPf (j, k + 1) end
end
local f = smallPf (n, 2) local q = math.floor (n / f)
if q == 1
then return 1
else return q * lagarias (f) + f * lagarias (q)
end
end
end
for n = -99,100
do io.write (string.format("%6d", lagarias (n)))
if n % 10 == 0 then io.write ("\n") end
end
io.write ("\n")
for n = 1,17 -- 18, 19 and 20 would overflow
do local m = 10 ^ n
io.write ("D(", string.format ("%d", m), ") / 7 = ", math.floor (lagarias (m) / 7), "\n")
end
end
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
D(10) / 7 = 1
D(100) / 7 = 20
D(1000) / 7 = 300
D(10000) / 7 = 4000
D(100000) / 7 = 50000
D(1000000) / 7 = 600000
D(10000000) / 7 = 7000000
D(100000000) / 7 = 80000000
D(1000000000) / 7 = 900000000
D(10000000000) / 7 = 10000000000
D(100000000000) / 7 = 110000000000
D(1000000000000) / 7 = 1200000000000
D(10000000000000) / 7 = 13000000000000
D(100000000000000) / 7 = 140000000000000
D(1000000000000000) / 7 = 1500000000000000
D(10000000000000000) / 7 = 16000000000000000
D(100000000000000000) / 7 = 170000000000000000
MiniScript
lagarias = function (n) // Lagarias arithmetic derivative
if n < 0 then
return -lagarias (-n)
else if n == 0 or n == 1 then
return 0
else
smallPf = function (j, k) // Smallest prime factor
if j % k == 0 then
return k
else
return smallPf (j, k + 1)
end if
end function
f = smallPf (n, 2)
q = floor (n / f)
if q == 1 then
return 1
else
return q * lagarias (f) + f * lagarias (q)
end if
end if
end function
fmt6 = function (n) // return a 6 character string representation of n
s = str( n )
if s.len > 5 then
return s
else
return ( " " * ( 6 - s.len ) ) + s
end if
end function
ad = ""
for n in range( -99, 100 )
ad = ad + " " + fmt6( lagarias (n) )
if n % 10 == 0 then
print( ad )
ad = ""
end if
end for
print()
for n in range( 1, 17 ) // 18, 19 and 20 would overflow ????? TODO: check
m = 10 ^ n
print( "D(" + str(m) + ") / 7 = " + str( floor (lagarias (m) / 7) ) )
end for
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
D(10) / 7 = 1
D(100) / 7 = 20
D(1000) / 7 = 300
D(10000) / 7 = 4000
D(100000) / 7 = 50000
D(1000000) / 7 = 600000
D(10000000) / 7 = 7000000
D(100000000) / 7 = 80000000
D(1000000000) / 7 = 900000000
D(10000000000) / 7 = 10000000000
D(100000000000) / 7 = 110000000000
D(1000000000000) / 7 = 1200000000000
D(10000000000000) / 7 = 13000000000000
D(100000000000000) / 7 = 140000000000000
D(1000000000000000) / 7 = 1500000000000000
D(10000000000000000) / 7 = 16000000000000000
D(100000000000000000) / 7 = 170000000000000000
D(1000000000000000000) / 7 = 1800000000000000000
D(10000000000000000000) / 7 = 19000000000000000000
D(100000000000000000000) / 7 = 200000000000000000000
Nim
import std/[strformat, strutils]
import integers
func aDerivative(n: int | Integer): typeof(n) =
## Recursively compute the arithmetic derivative.
## The function works with normal integers or big integers.
## Using a cache to store the derivatives would improve the
## performance, but this is not needed for these tasks.
if n < 0: return -aDerivative(-n)
if n == 0 or n == 1: return 0
if n == 2: return 1
var d = 2
result = 1
while d * d <= n:
if n mod d == 0:
let q = n div d
result = q * aDerivative(d) + d * aDerivative(q)
break
inc d
### Task ###
echo "Arithmetic derivatives for -99 through 100:"
# We can use an "int" variable here.
var col = 0
for n in -99..100:
inc col
stdout.write &"{aDerivative(n):>4}"
stdout.write if col == 10: '\n' else: ' '
if col == 10: col = 0
### Stretch task ###
echo()
# To avoid overflow, we have to use an "Integer" variable.
var n = Integer(1)
for m in 1..20:
n *= 10
let a = aDerivative(n)
let left = &"D(10^{m}) / 7"
echo &"{left:>12} = {a div 7}"
- Output:
Arithmetic derivatives for -99 through 100: -75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^1) / 7 = 1 D(10^2) / 7 = 20 D(10^3) / 7 = 300 D(10^4) / 7 = 4000 D(10^5) / 7 = 50000 D(10^6) / 7 = 600000 D(10^7) / 7 = 7000000 D(10^8) / 7 = 80000000 D(10^9) / 7 = 900000000 D(10^10) / 7 = 10000000000 D(10^11) / 7 = 110000000000 D(10^12) / 7 = 1200000000000 D(10^13) / 7 = 13000000000000 D(10^14) / 7 = 140000000000000 D(10^15) / 7 = 1500000000000000 D(10^16) / 7 = 16000000000000000 D(10^17) / 7 = 170000000000000000 D(10^18) / 7 = 1800000000000000000 D(10^19) / 7 = 19000000000000000000 D(10^20) / 7 = 200000000000000000000
Perl
use v5.36;
use bigint;
no warnings 'uninitialized';
use List::Util 'max';
use ntheory 'factor';
sub table ($c, @V) { my $t = $c * (my $w = 2 + length max @V); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
sub D ($n) {
my(%f, $s);
$f{$_}++ for factor max 1, my $nabs = abs $n;
map { $s += $nabs * $f{$_} / $_ } keys %f;
$n > 0 ? $s : -$s;
}
say table 10, map { D $_ } -99 .. 100;
say join "\n", map { sprintf('D(10**%-2d) / 7 == ', $_) . D(10**$_) / 7 } 1 .. 20;
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
D(10**1 ) / 7 == 1
D(10**2 ) / 7 == 20
D(10**3 ) / 7 == 300
D(10**4 ) / 7 == 4000
D(10**5 ) / 7 == 50000
D(10**6 ) / 7 == 600000
D(10**7 ) / 7 == 7000000
D(10**8 ) / 7 == 80000000
D(10**9 ) / 7 == 900000000
D(10**10) / 7 == 10000000000
D(10**11) / 7 == 110000000000
D(10**12) / 7 == 1200000000000
D(10**13) / 7 == 13000000000000
D(10**14) / 7 == 140000000000000
D(10**15) / 7 == 1500000000000000
D(10**16) / 7 == 16000000000000000
D(10**17) / 7 == 170000000000000000
D(10**18) / 7 == 1800000000000000000
D(10**19) / 7 == 19000000000000000000
D(10**20) / 7 == 200000000000000000000
Phix
with javascript_semantics include mpfr.e procedure D(mpz n) integer s = mpz_cmp_si(n,0) if s<0 then mpz_neg(n,n) end if if mpz_cmp_si(n,2)<0 then mpz_set_si(n,0) else sequence f = mpz_prime_factors(n) integer c = sum(vslice(f,2)), f1 = f[1][1] if c=1 then mpz_set_si(n,1) elsif c=2 then mpz_set_si(n,f1 + iff(length(f)=1?f1:f[2][1])) else assert(mpz_fdiv_q_ui(n,n,f1)=0) mpz d = mpz_init_set(n) D(n) mpz_mul_si(n,n,f1) mpz_add(n,n,d) end if if s<0 then mpz_neg(n,n) end if end if end procedure sequence res = repeat(0,200) mpz n = mpz_init() for i=-99 to 100 do mpz_set_si(n,i) D(n) res[i+100] = mpz_get_str(n) end for printf(1,"%s\n\n",{join_by(res,1,10," ",fmt:="%4s")}) for m=1 to 20 do mpz_ui_pow_ui(n,10,m) D(n) assert(mpz_fdiv_q_ui(n,n,7)=0) printf(1,"D(10^%d)/7 = %s\n",{m,mpz_get_str(n)}) end for
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^1)/7 = 1 D(10^2)/7 = 20 D(10^3)/7 = 300 D(10^4)/7 = 4000 D(10^5)/7 = 50000 D(10^6)/7 = 600000 D(10^7)/7 = 7000000 D(10^8)/7 = 80000000 D(10^9)/7 = 900000000 D(10^10)/7 = 10000000000 D(10^11)/7 = 110000000000 D(10^12)/7 = 1200000000000 D(10^13)/7 = 13000000000000 D(10^14)/7 = 140000000000000 D(10^15)/7 = 1500000000000000 D(10^16)/7 = 16000000000000000 D(10^17)/7 = 170000000000000000 D(10^18)/7 = 1800000000000000000 D(10^19)/7 = 19000000000000000000 D(10^20)/7 = 200000000000000000000
Python
from sympy.ntheory import factorint
def D(n):
if n < 0:
return -D(-n)
elif n < 2:
return 0
else:
fdict = factorint(n)
if len(fdict) == 1 and 1 in fdict: # is prime
return 1
return sum([n * e // p for p, e in fdict.items()])
for n in range(-99, 101):
print('{:5}'.format(D(n)), end='\n' if n % 10 == 0 else '')
print()
for m in range(1, 21):
print('(D for 10**{}) divided by 7 is {}'.format(m, D(10 ** m) // 7))
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
(D for 10**1) divided by 7 is 1
(D for 10**2) divided by 7 is 20
(D for 10**3) divided by 7 is 300
(D for 10**4) divided by 7 is 4000
(D for 10**5) divided by 7 is 50000
(D for 10**6) divided by 7 is 600000
(D for 10**7) divided by 7 is 7000000
(D for 10**8) divided by 7 is 80000000
(D for 10**9) divided by 7 is 900000000
(D for 10**10) divided by 7 is 10000000000
(D for 10**11) divided by 7 is 110000000000
(D for 10**12) divided by 7 is 1200000000000
(D for 10**13) divided by 7 is 13000000000000
(D for 10**14) divided by 7 is 140000000000000
(D for 10**15) divided by 7 is 1500000000000000
(D for 10**16) divided by 7 is 16000000000000000
(D for 10**17) divided by 7 is 170000000000000000
(D for 10**18) divided by 7 is 1800000000000000000
(D for 10**19) divided by 7 is 19000000000000000000
(D for 10**20) divided by 7 is 200000000000000000000
Quackery
primefactors is defined at Prime decomposition#Quackery.
[ dup 0 < iff
[ negate
' negate ]
else []
swap 0 over
primefactors
witheach
[ dip over / + ]
nip swap do ] is d ( n --> n )
200 times [ i^ 99 - d echo sp ]
cr cr
20 times [ 10 i^ 1+ ** d 7 / echo cr ]- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 1 20 300 4000 50000 600000 7000000 80000000 900000000 10000000000 110000000000 1200000000000 13000000000000 140000000000000 1500000000000000 16000000000000000 170000000000000000 1800000000000000000 19000000000000000000 200000000000000000000
Raku
use Prime::Factor;
multi D (0) { 0 }
multi D (1) { 0 }
multi D ($n where &is-prime) { 1 }
multi D ($n where * < 0 ) { -D -$n }
multi D ($n) { sum $n.&prime-factors.Bag.map: { $n × .value / .key } }
put (-99 .. 100).map(&D).batch(10)».fmt("%4d").join: "\n";
put '';
put join "\n", (1..20).map: { sprintf "D(10**%-2d) / 7 == %d", $_, D(10**$_) / 7 }
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10**1 ) / 7 == 1 D(10**2 ) / 7 == 20 D(10**3 ) / 7 == 300 D(10**4 ) / 7 == 4000 D(10**5 ) / 7 == 50000 D(10**6 ) / 7 == 600000 D(10**7 ) / 7 == 7000000 D(10**8 ) / 7 == 80000000 D(10**9 ) / 7 == 900000000 D(10**10) / 7 == 10000000000 D(10**11) / 7 == 110000000000 D(10**12) / 7 == 1200000000000 D(10**13) / 7 == 13000000000000 D(10**14) / 7 == 140000000000000 D(10**15) / 7 == 1500000000000000 D(10**16) / 7 == 16000000000000000 D(10**17) / 7 == 170000000000000000 D(10**18) / 7 == 1800000000000000000 D(10**19) / 7 == 19000000000000000000 D(10**20) / 7 == 200000000000000000000
RPL
≪ CASE
DUP 0 < THEN NEG ADERIV NEG END
DUP 2 < THEN DROP 0 END
R→I DUP ISPRIME? THEN DROP 1 END
DUP FACTORS HEAD LASTARG 2 GET DUP2 ^ 4 PICK OVER / 1 RND
→ n p k pk rem
≪ k pk p / * rem * rem ADERIV pk * +
≫
END
≫ 'ADERIV' STO
≪ n ADERIV ≫ 'n' -99 100 1 SEQ ≪ 10 m ^ ADERIV 7 / R→I ≫ 'nm' 1 20 1 SEQ
- Output:
2: {-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140}
1: {1 20 300 4000 50000 600000 7000000 80000000 900000000 10000000000 110000000000 1200000000000 13000000000000 140000000000000 1500000000000000 16000000000000000 170000000000000000 800000000000000000 19000000000000000000 200000000000000000000}
Rust
use prime_factorization::Factorization;
fn d(n: i128) -> i128 {
if n < 0 {
return -(d(-n));
} else if n < 2 {
return 0;
} else {
let fpairs = Factorization::run(n as u128).prime_factor_repr();
if fpairs.len() == 1 && fpairs[0].1 == 1 {
return 1;
}
return fpairs.iter().fold(0_i128, |p, q| p + n * (q.1 as i128) / (q.0 as i128));
}
}
fn main() {
for n in -99..101 {
print!("{:5}{}", d(n), { if n % 10 == 0 { "\n" } else {""} });
}
println!();
for m in 1..21 {
println!("(D for 10 ^ {}) divided by 7 is {}", m, d(10_i128.pow(m)) / 7)
}
}
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123
-1 -140 -32 -45 -22 -124 -1 -43 -108 -176
-1 -71 -18 -80 -55 -39 -1 -156 -1 -59
-26 -72 -1 -61 -18 -192 -51 -33 -1 -92
-1 -31 -22 -92 -16 -81 -1 -56 -20 -45
-14 -112 -1 -25 -39 -48 -1 -41 -1 -68
-16 -21 -1 -60 -12 -19 -14 -80 -1 -31
-1 -32 -27 -15 -10 -44 -1 -13 -10 -24
-1 -21 -1 -32 -8 -9 -1 -16 -1 -7
-6 -12 -1 -5 -1 -4 -1 -1 0 0
0 1 1 4 1 5 1 12 6 7
1 16 1 9 8 32 1 21 1 24
10 13 1 44 10 15 27 32 1 31
1 80 14 19 12 60 1 21 16 68
1 41 1 48 39 25 1 112 14 45
20 56 1 81 16 92 22 31 1 92
1 33 51 192 18 61 1 72 26 59
1 156 1 39 55 80 18 71 1 176
108 43 1 124 22 45 32 140 1 123
20 96 34 49 24 272 1 77 75 140
(D for 10 ^ 1) divided by 7 is 1
(D for 10 ^ 2) divided by 7 is 20
(D for 10 ^ 3) divided by 7 is 300
(D for 10 ^ 4) divided by 7 is 4000
(D for 10 ^ 5) divided by 7 is 50000
(D for 10 ^ 6) divided by 7 is 600000
(D for 10 ^ 7) divided by 7 is 7000000
(D for 10 ^ 8) divided by 7 is 80000000
(D for 10 ^ 9) divided by 7 is 900000000
(D for 10 ^ 10) divided by 7 is 10000000000
(D for 10 ^ 11) divided by 7 is 110000000000
(D for 10 ^ 12) divided by 7 is 1200000000000
(D for 10 ^ 13) divided by 7 is 13000000000000
(D for 10 ^ 14) divided by 7 is 140000000000000
(D for 10 ^ 15) divided by 7 is 1500000000000000
(D for 10 ^ 16) divided by 7 is 16000000000000000
(D for 10 ^ 17) divided by 7 is 170000000000000000
(D for 10 ^ 18) divided by 7 is 1800000000000000000
(D for 10 ^ 19) divided by 7 is 19000000000000000000
(D for 10 ^ 20) divided by 7 is 200000000000000000000
Scala
import java.math.BigInteger
object ArithmeticDerivative extends App {
println("Arithmetic derivatives for -99 to 100 inclusive:")
for {
n <- -99 to 100
column = n + 100
} print(f"${derivative(BigInteger.valueOf(n))}%4d${if (column % 10 == 0) "\n" else " "}")
println()
val seven = BigInteger.valueOf(7)
for (power <- 1 to 20) {
println(f"D(10^$power%d) / 7 = ${derivative(BigInteger.TEN.pow(power)).divide(seven)}")
}
def derivative(aNumber: BigInteger): BigInteger = {
if (aNumber.signum == -1) {
return derivative(aNumber.negate()).negate()
}
if (aNumber == BigInteger.ZERO || aNumber == BigInteger.ONE) {
return BigInteger.ZERO
}
var divisor = BigInteger.TWO
while (divisor.multiply(divisor).compareTo(aNumber) <= 0) {
if (aNumber.mod(divisor).signum == 0) {
val quotient = aNumber.divide(divisor)
return quotient.multiply(derivative(divisor)).add(divisor.multiply(derivative(quotient)))
}
divisor = divisor.add(BigInteger.ONE)
}
BigInteger.ONE
}
}
- Output:
Arithmetic derivatives for -99 to 100 inclusive: -75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^1) / 7 = 1 D(10^2) / 7 = 20 D(10^3) / 7 = 300 D(10^4) / 7 = 4000 D(10^5) / 7 = 50000 D(10^6) / 7 = 600000 D(10^7) / 7 = 7000000 D(10^8) / 7 = 80000000 D(10^9) / 7 = 900000000 D(10^10) / 7 = 10000000000 D(10^11) / 7 = 110000000000 D(10^12) / 7 = 1200000000000 D(10^13) / 7 = 13000000000000 D(10^14) / 7 = 140000000000000 D(10^15) / 7 = 1500000000000000 D(10^16) / 7 = 16000000000000000 D(10^17) / 7 = 170000000000000000 D(10^18) / 7 = 1800000000000000000 D(10^19) / 7 = 19000000000000000000 D(10^20) / 7 = 200000000000000000000
Wren
As integer arithmetic in Wren is inaccurate above 2^53 we need to use BigInt here.
import "./big" for BigInt
import "./fmt" for Fmt
var D = Fn.new { |n|
if (n < 0) return -D.call(-n)
if (n < 2) return BigInt.zero
var f = BigInt.primeFactors(n)
var c = f.count
if (c == 1) return BigInt.one
if (c == 2) return f[0] + f[1]
var d = n / f[0]
return D.call(d) * f[0] + d
}
var ad = List.filled(200, 0)
for (n in -99..100) ad[n+99] = D.call(BigInt.new(n))
Fmt.tprint("$4i", ad, 10)
System.print()
for (m in 1..20) {
Fmt.print("D(10^$-2d) / 7 = $i", m, D.call(BigInt.ten.pow(m))/7)
}
- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140 D(10^1 ) / 7 = 1 D(10^2 ) / 7 = 20 D(10^3 ) / 7 = 300 D(10^4 ) / 7 = 4000 D(10^5 ) / 7 = 50000 D(10^6 ) / 7 = 600000 D(10^7 ) / 7 = 7000000 D(10^8 ) / 7 = 80000000 D(10^9 ) / 7 = 900000000 D(10^10) / 7 = 10000000000 D(10^11) / 7 = 110000000000 D(10^12) / 7 = 1200000000000 D(10^13) / 7 = 13000000000000 D(10^14) / 7 = 140000000000000 D(10^15) / 7 = 1500000000000000 D(10^16) / 7 = 16000000000000000 D(10^17) / 7 = 170000000000000000 D(10^18) / 7 = 1800000000000000000 D(10^19) / 7 = 19000000000000000000 D(10^20) / 7 = 200000000000000000000
XPL0
function integer Lagarias (N); \Lagarias arithmetic derivative
integer N;
integer F, Q;
function integer SmallPF (J, K); \Smallest prime factor
integer J, K;
return if rem(J/K) = 0 then K else SmallPF(J, K+1);
begin
if N < 0
then return -Lagarias (-N)
else if N = 0 or N = 1
then return 0
else begin
F := SmallPF (N, 2); Q := N / F;
return if Q = 1
then 1
else Q * Lagarias (F) + F * Lagarias (Q)
end;
end \Lagarias\ ;
integer N;
begin
for N:= -99 to 100 do begin
IntOut(0, Lagarias(N) );
if rem(N/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
end;
end- Output:
-75 -77 -1 -272 -24 -49 -34 -96 -20 -123 -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 -6 -12 -1 -5 -1 -4 -1 -1 0 0 0 1 1 4 1 5 1 12 6 7 1 16 1 9 8 32 1 21 1 24 10 13 1 44 10 15 27 32 1 31 1 80 14 19 12 60 1 21 16 68 1 41 1 48 39 25 1 112 14 45 20 56 1 81 16 92 22 31 1 92 1 33 51 192 18 61 1 72 26 59 1 156 1 39 55 80 18 71 1 176 108 43 1 124 22 45 32 140 1 123 20 96 34 49 24 272 1 77 75 140