Arithmetic derivative
(Redirected from Arithmetic Derivative)
You are encouraged to solve this task according to the task description, using any language you may know.
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:
- 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
Mathematica / Wolfram Language
(* Arithmetic derivative *)
ClearAll[d, twoFactorsOf];
twoFactorsOf[n_Integer?Positive] := Module[{factors = FactorInteger[n, 2], p, factor},
If[Length[factors] == 1,
factor = Flatten@factors;
p = First@factor;
factors = {factor - {0, 1}, {p, 1}};
];
Return[Power@@@factors];
];
twoFactorsOf[n_Integer?Negative] := twoFactorsOf[-n] * {-1, -1};
d[0] = d[1] = 0;
d[p_Integer?PrimeQ] := 1;
d[n_Integer?Negative] := -d[-n];
d[mn_Integer] := Module[{m, n},
{m, n} = twoFactorsOf[m n];
Return[d[m] n + m d[n]];
];
SetAttributes[d, Listable];
(* Output *)
Partition[StringPadLeft[ToString /@ d[Range[-99, 100]], 5], UpTo[10]] // TableForm
StringJoin["d[10^", ToString@First[#], "]", If[First[#] <= 9, " ", " "], "/ 7",
" = ",
ToString@Last[#]] & /@ Table[{n, d[10^n]/7}, {n, 1, 20}] // TableForm
- Output:
57 -21 1 -80 -24 -49 -34 88 -20 -33
1 -52 -32 -45 -22 -68 1 -43 -54 64
1 59 -18 72 5 -39 1 12 1 39
-26 64 1 49 -18 -64 33 -33 1 -52
1 -31 -22 -36 -16 -45 1 48 -20 -5
-14 32 1 -25 21 40 1 29 1 -28
-16 -21 1 60 -12 -19 -14 16 1 19
1 24 9 -15 -10 -20 1 -13 -10 16
1 3 1 -16 -8 -9 1 8 1 -7
-6 4 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] = 1
d[10^2] = 20
d[10^3] = 300
d[10^4] = 4000
d[10^5] = 50000
d[10^6] = 600000
d[10^7] = 7000000
d[10^8] = 80000000
d[10^9] = 900000000
d[10^10] = 10000000000
d[10^11] = 110000000000
d[10^12] = 1200000000000
d[10^13] = 13000000000000
d[10^14] = 140000000000000
d[10^15] = 1500000000000000
d[10^16] = 16000000000000000
d[10^17] = 170000000000000000
d[10^18] = 1800000000000000000
d[10^19] = 19000000000000000000
d[10^20] = 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
R
library(gmp) #for big number factorization
arithmetic_derivative<-function(x){
if (x==0|x==1|x==-1){
D=0
}
else{
n=ifelse(x<0,-x,x)
prime_decomposition <-as.numeric(factorize(n))
if (length(prime_decomposition)==1){
D<- 1
}
else{
D<-sum(prime_decomposition[c(1,2)])
if (length(prime_decomposition)>2){
cumulative_prod <-cumprod(prime_decomposition)
for (i in 3:length(prime_decomposition)){
D<- D * prime_decomposition[i] + cumulative_prod[i-1]
}
}
}
}
sign(x)*D
}
print(t(matrix(sapply(-99:100,arithmetic_derivative),nrow=10)))
for (k in 1:20){
x <- 10**k
cat(paste0("D(",x,")/7 = ",arithmetic_derivative(x)/7,"\n"),sep = "")}
Output
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] -75 -77 -1 -272 -24 -49 -34 -96 -20 -123 [2,] -1 -140 -32 -45 -22 -124 -1 -43 -108 -176 [3,] -1 -71 -18 -80 -55 -39 -1 -156 -1 -59 [4,] -26 -72 -1 -61 -18 -192 -51 -33 -1 -92 [5,] -1 -31 -22 -92 -16 -81 -1 -56 -20 -45 [6,] -14 -112 -1 -25 -39 -48 -1 -41 -1 -68 [7,] -16 -21 -1 -60 -12 -19 -14 -80 -1 -31 [8,] -1 -32 -27 -15 -10 -44 -1 -13 -10 -24 [9,] -1 -21 -1 -32 -8 -9 -1 -16 -1 -7 [10,] -6 -12 -1 -5 -1 -4 -1 -1 0 0 [11,] 0 1 1 4 1 5 1 12 6 7 [12,] 1 16 1 9 8 32 1 21 1 24 [13,] 10 13 1 44 10 15 27 32 1 31 [14,] 1 80 14 19 12 60 1 21 16 68 [15,] 1 41 1 48 39 25 1 112 14 45 [16,] 20 56 1 81 16 92 22 31 1 92 [17,] 1 33 51 192 18 61 1 72 26 59 [18,] 1 156 1 39 55 80 18 71 1 176 [19,] 108 43 1 124 22 45 32 140 1 123 [20,] 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(1e+05)/7 = 50000 D(1e+06)/7 = 6e+05 D(1e+07)/7 = 7e+06 D(1e+08)/7 = 8e+07 D(1e+09)/7 = 9e+08 D(1e+10)/7 = 1e+10 D(1e+11)/7 = 1.1e+11 D(1e+12)/7 = 1.2e+12 D(1e+13)/7 = 1.3e+13 D(1e+14)/7 = 1.4e+14 D(1e+15)/7 = 1.5e+15 D(1e+16)/7 = 1.6e+16 D(1e+17)/7 = 1.7e+17 D(1e+18)/7 = 1.8e+18 D(1e+19)/7 = 1.9e+19 D(1e+20)/7 = 2e+20
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