cp's OEIS Frontend

A160112 Number of cubefree integers not exceeding 10^n.

%I A160112 #29 Aug 08 2024 11:12:14
%S A160112 1,9,85,833,8319,83190,831910,8319081,83190727,831907372,8319073719,
%T A160112 83190737244,831907372522,8319073725828,83190737258105,
%U A160112 831907372580692,8319073725807178,83190737258070643,831907372580707771
%N A160112 Number of cubefree integers not exceeding 10^n.
%C A160112 An alternate definition specifying "less than 10^n" would yield the same sequence except for the first 3 terms: 0, 8, 84, 833, 8319, etc. (since powers of 10 beyond 1000 are not cubefree anyhow).
%C A160112 The limit of a(n)/10^n is the inverse of Apery's constant, 1/zeta(3), whose digits are given by A088453.
%H A160112 Chai Wah Wu, <a href="/A160112/b160112.txt">Table of n, a(n) for n = 0..31</a> (terms 0..29 from Gerard P. Michon)
%H A160112 Gerard P. Michon, <a href="http://www.numericana.com/answer/counting.htm#cubefree">On the number of cubefree integers not exceeding N</a>.
%F A160112 a(n) = Sum_{i=1..floor(10^(n/3))} A008683(i)*floor(10^n/i^3).
%e A160112 a(0)=1 because 1 <= 10^0 is not a multiple of the cube of a prime.
%e A160112 a(1)=9 because the 9 numbers 1,2,3,4,5,6,7,9,10 are cubefree; 8 is not.
%e A160112 a(2)=85 because there are 85 cubefree integers equal to 100 or less.
%e A160112 a(3)=833 because there are 833 cubefree integers below 1000 (which is not cubefree itself).
%p A160112 with(numtheory): A160112:=n->add(mobius(i)*floor(10^n/(i^3)), i=1..10^n): (1,9,85,seq(A160112(n), n=3..5)); # _Wesley Ivan Hurt_, Aug 01 2015
%t A160112 Table[ Sum[ MoebiusMu[x]*Floor[10^n/(x^3)], {x, 10^(n/3)}], {n, 0, 18}] (* _Robert G. Wilson v_, May 27 2009 *)
%o A160112 (Python)
%o A160112 from sympy import mobius, integer_nthroot
%o A160112 def A160112(n): return sum(mobius(k)*(10**n//k**3) for k in range(1, integer_nthroot(10**n,3)[0]+1)) # _Chai Wah Wu_, Aug 06 2024
%o A160112 (Python)
%o A160112 from bitarray import bitarray
%o A160112 from sympy import integer_nthroot
%o A160112 def A160112(n): # faster program
%o A160112     q = 10**n
%o A160112     m = integer_nthroot(q,3)[0]+1
%o A160112     a, b = bitarray(m), bitarray(m)
%o A160112     a[1], p, i, c = 1, 2, 4, q-sum(q//k**3 for k in range(2,m))
%o A160112     while i < m:
%o A160112         j = 2
%o A160112         while i < m:
%o A160112             if j==p:
%o A160112                 c -= (b[i]^1 if a[i] else -1)*(q//i**3)
%o A160112                 j, a[i], b[i] = 0, 1, 1
%o A160112             else:
%o A160112                 t1, t2 = a[i], b[i]
%o A160112                 if (t1&t2)^1:
%o A160112                     a[i], b[i] = (t1^1)&t2, ((t1^1)&t2)^1
%o A160112                     c += (t2 if t1 else 2)*(q//i**3) if (t1^1)&t2 else (t2-2 if t1 else 0)*(q//i**3)
%o A160112             i += p
%o A160112             j += 1
%o A160112         p += 1
%o A160112         while a[p]|b[p]:
%o A160112             p += 1
%o A160112         i = p<<1
%o A160112     return c # _Chai Wah Wu_, Aug 06 2024
%Y A160112 A004709 (cubefree numbers). A088453 (limit of the string of digits). A160113 (binary counterpart for cubefree integers). A071172 & A053462 (decimal counterpart for squarefree integers). A143658 (binary counterpart for squarefree integers).
%K A160112 easy,nice,nonn
%O A160112 0,2
%A A160112 _Gerard P. Michon_, May 02 2009, May 06 2009