login
Number of integer solutions to x' = n, where x' is the arithmetic derivative of x.
21

%I #33 Jan 22 2024 15:30:57

%S 0,0,1,1,1,1,1,1,2,0,2,1,2,1,3,0,2,1,2,2,3,0,4,1,3,1,2,0,3,2,4,1,4,0,

%T 4,0,2,2,3,1,4,1,4,2,4,0,6,1,4,1,3,0,5,2,4,0,4,1,7,2,3,1,5,0,6,0,3,1,

%U 5,2,7,1,5,3,5,1,7,0,6,2,5,0,8,1,5,2,4,0,9,3,6,0,5,1,8,0,3,1,6,2,8,2,5,1,6

%N Number of integer solutions to x' = n, where x' is the arithmetic derivative of x.

%C This is the i(n) function in the paper by Ufnarovski and Ahlander. Note that a(1) is infinite because all primes satisfy x' = 1. The plot shows the great difference in the number of solutions for even and odd n. Also compare sequence A189558, which gives the least number have n solutions, and A189560, which gives the least such odd number.

%C It appears that there are a finite number of even numbers having a given number of solutions. This conjecture is explored in A189561 and A189562.

%D See A003415

%H Antti Karttunen, <a href="/A099302/b099302.txt">Table of n, a(n) for n = 2..100000</a> (terms 2..40000 from T. D. Noe)

%H Victor Ufnarovski and Bo Ahlander, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarovski.html">How to Differentiate a Number</a>, J. Integer Seqs., Vol. 6, 2003.

%F a(A098700(n)) = 0; a(A239433(n)) > 0. - _Reinhard Zumkeller_, Mar 18 2014

%F From _Antti Karttunen_, Jan 21 2024: (Start)

%F a(n) = Sum_{i=1..A002620(n)} [A003415(i)==n], where [ ] is the Iverson bracket.

%F a(2n) >= A002375(n), a(2n+1) >= A369054(2n+1).

%F (End)

%t dn[0]=0; dn[1]=0; dn[n_]:=Module[{f=Transpose[FactorInteger[n]]}, If[PrimeQ[n], 1, Plus@@(n*f[[2]]/f[[1]])]]; d1=Table[dn[n], {n, 40000}]; Table[Count[d1, n], {n, 2, 400}]

%o (Haskell)

%o a099302 n = length $ filter (== n) $ map a003415 [1 .. a002620 n]

%o -- _Reinhard Zumkeller_, Mar 18 2014

%o (Python)

%o from sympy import factorint

%o def A099302(n): return sum(1 for m in range(1,(n**2>>2)+1) if sum((m*e//p for p,e in factorint(m).items())) == n) # _Chai Wah Wu_, Sep 12 2022

%o (PARI)

%o up_to = 100000; \\ A002620(10^5) = 2500000000

%o A002620(n) = ((n^2)>>2);

%o A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));

%o A099302list(up_to) = { my(d,c,v=vector(up_to)); for(i=1, A002620(up_to), d = A003415(i); if(d>1 && d<=up_to, v[d]++)); (v); };

%o v099302 = A099302list(up_to);

%o A099302(n) = v099302[n]; \\ _Antti Karttunen_, Jan 21 2024

%Y Cf. A002620, A003415 (arithmetic derivative of n), A099303 (greatest x such that x' = n), A098699 (least x such that x' = n), A098700 (n such that x' = n has no integer solution), A239433 (n such that x' = n has at least one solution).

%Y Cf. A002375 (a lower bound for even n), A369054 (a lower bound for n of the form 4m+3).

%K nonn,look

%O 2,9

%A _T. D. Noe_, Oct 12 2004, Apr 24 2011