login
a(n) = median of the largest prime dividing a random n-digit number.
2

%I #30 Mar 13 2021 00:58:32

%S 3,12,53,229,947,3863,15731,63823,258737

%N a(n) = median of the largest prime dividing a random n-digit number.

%C A randomly selected n-digit number (uniformly distributed on 10^(n-1) to 10^n-1) has at least a 50% probability of having a prime factor at least as large as a(n).

%C For n >= 2 the number m = 9*10^(n-1) of n-digit numbers is even. The median is taken to be the average of the (m/2)-th and (m/2+1)-th of the sorted list of largest prime factors. - _Robert Israel_, Dec 11 2015

%D D. E. Knuth, The Art of Computer Programming, Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1969, Vol. 2.

%e The largest prime divisors of the nonunit 1-digit numbers are 2, 3, 2, 5, 3, 7, 2 and 3 respectively, with median 3.

%e Of the 90 2-digit numbers, there are 45 whose largest prime divisor is 11 or less and 45 whose largest prime divisor is 13 or greater, so any of 11, 12, or 13 could be used for the second term, although the arithmetic average of the endpoints is commonly used.

%p seq(Statistics:-Median([seq(max(numtheory:-factorset(n)),n=10^(d-1)..10^d-1)]),d=1..7); # _Robert Israel_, Dec 11 2015

%t f[n_] := Block[{k = If[n == 1, 1, 0], lst = {}, pt = 10^(n - 1)}, While[k < 9*pt, AppendTo[lst, FactorInteger[pt + k][[ -1, 1]]]; k++ ]; Median@ lst]; (* _Robert G. Wilson v_, Dec 14 2006 *)

%o (GAUSS)

%o n = 1;

%o a = 2 | 3 | 2 | 5 | 3 | 7 | 2 | 3;

%o meana = meanc(a);

%o mediana = median(a);

%o format /rdn 1,0;

%o print n;; "-digit numbers:";

%o print " Median = ";; mediana;

%o format /rdn 10,5;

%o print " Mean = ";; meana;

%o print;

%o b = 1 | a;

%o dim = 1;

%o _01: wait;

%o n = n+1;

%o dim = 10*dim;

%o a = b | zeros(9*dim,1);

%o i = dim;

%o do until i == 10*dim;

%o if i == 2*floor(i/2);

%o a[i] = a[i/2];

%o else;

%o p = firstp(i);

%o if p == i;

%o a[i] = i;

%o else;

%o a[i] = a[i/p];

%o endif;

%o endif;

%o i = i+1;

%o endo;

%o b = a[dim:10*dim-1];

%o meana = meanc(b);

%o mediana = median(b);

%o format /rdn 1,0;

%o print n;; "-digit numbers:";

%o print " Median = ";; mediana;

%o format /rdn 10,5;

%o print " Mean = ";; meana;

%o print;

%o b = a;

%o goto _01;

%o proc firstp(n);

%o local i;

%o i = 3;

%o do until i > sqrt(n);

%o if n == i*floor(n/i);

%o retp(i);

%o endif;

%o i = i+2;

%o endo;

%o retp(n);

%o endp;

%o (MATLAB)

%o P = primes(10^8);

%o L = zeros(1,10^8);

%o for p = P

%o L([p:p:10^8]) = p;

%o end

%o A(1) = median(L(2:9));

%o for d = 2:8

%o A(d) = median(L(10^(d-1):10^d-1));

%o end

%o A % _Robert Israel_, Dec 11 2015

%o (Python)

%o from sympy import factorint

%o from statistics import median

%o def a(n):

%o lb, ub = max(2, 10**(n-1)), 10**n

%o return int(round(median([max(factorint(i)) for i in range(lb, ub)])))

%o print([a(n) for n in range(1, 6)]) # _Michael S. Branicky_, Mar 12 2021

%Y Cf. A006530, A046731, A126282.

%K base,more,nonn

%O 1,1

%A Mark Thornquist (mthornqu(AT)fhcrc.org), Dec 07 2006

%E Edited by _Robert G. Wilson v_, Dec 14 2006

%E a(8) from _Robert Israel_, Dec 11 2015

%E a(9) from _Giovanni Resta_, Apr 19 2016