A007843 Least positive integer k for which 2^n divides k!.

1, 2, 4, 4, 6, 8, 8, 8, 10, 12, 12, 14, 16, 16, 16, 16, 18, 20, 20, 22, 24, 24, 24, 26, 28, 28, 30, 32, 32, 32, 32, 32, 34, 36, 36, 38, 40, 40, 40, 42, 44, 44, 46, 48, 48, 48, 48, 50, 52, 52, 54, 56, 56, 56, 58, 60, 60, 62, 64, 64, 64, 64, 64, 64, 66, 68, 68, 70, 72, 72, 72, 74, 76, 76, 78

Offset: 0

Author

Bruce Dearden and Jerry Metzger; R. Muller

Keywords

• nonn
• easy
• nice

Comments

Obtained by writing every natural number n k times where 2^k divides n but 2^(k+1) does not divide n. - Amarnath Murthy, Aug 22 2002

An interval of the form (A007814(k!)-A007814(k), A007814(k!)] contains n >= 1 iff k = a(n). - Vladimir Shevelev, Mar 19 2012

It appears than for n > 0, a(n) is divisible by 2, and that the resulting sequence a(n)/2 is A046699 (ignoring first term, this is the Meta-Fibonacci sequence for s=0). - Michel Marcus, Aug 19 2013

The last part is proved in the Kullmann & Zhao preprint, Thm. 3.16. The first statement is obvious: to get a larger power of two in k!, k > 1 must be increased by 2, else the factor is odd and doesn't increase the 2-valuation of k!. The other part also follows from the comment in A046699: "n occurs A001511(n) times", where A001511 = A007814 + 1, A007814 = the number of powers of 2 in k. - M. F. Hasler, Dec 27 2019

References

• H. Ibstedt, Smarandache Primitive Numbers, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 216-229.

Links

• T. D. Noe, Table of n, a(n) for n = 0..1000
• Oliver Kullmann and Xishun Zhao, Parameters for minimal unsatisfiability: Smarandache primitive numbers and full clauses, arXiv preprint arXiv:1505.02318 [cs.DM], 2015.
• Kevin Ryde, PARI/GP Code and Notes
• F. Smarandache, Only Problems, Not Solutions!.
• Wikipedia, Legendre's Formula.

Crossrefs

Cf. A007814, A007844, A007845, A020646, A048841-A048846.

Programs

Maple

with(numtheory): ans := [ ]: p := ithprime(1): t0 := 1/p: for n from 0 to 50 do t0 := t0*p: t1 := 1: i := 1: while t1 mod t0 <> 0 do i := i+1: t1 := t1*i: od: ans := [ op(ans),i ]: od: ans;
# Alternative:
N:= 1000: # to get a(0) to a(N)
A:= Array(0..N):
A[0]:= 1:
A[1]:= 2:
B[2]:= 1:
for k from 4 by 2 do
  B[k]:= B[k-2] + padic:-ordp(k,2);
  A[B[k-2]+1..min(N,B[k])]:= k;
  if B[k] >= N then break fi;
od:
seq(A[i],i=0..N); # Robert Israel, Dec 07 2015

Mathematica

a[n_] := (k=0; While[Mod[++k!, 2^n] > 0]; k); Table[a[n], {n, 0, 74}] (* Jean-François Alcover, Dec 08 2011 *)
Join[{1},Module[{nn=100,f},f=Table[{x!,x},{x,0,nn}];Table[ SelectFirst[ f,Divisible[#[[1]],2^n]&],{n,80}]][[All,2]]] (* Harvey P. Dale, Nov 20 2021 *)

PARI

a(n)=if(n<0,0,s=1; while(s!%(2^n)>0,s++); s)

PARI

a(n) = {k = 1; while (valuation(k!, 2) < n, k++); k;} \\ Michel Marcus, Aug 19 2013

PARI

apply( A007843(n)={for(k=1,oo,(n-=valuation(k,2))>0||return(k))}, [0..99]) \\ This idea can also be used to compute most efficiently a vector a(0..N). - M. F. Hasler, Dec 27 2019

Python

from itertools import count
def A007843(n):
    c = 0
    for k in count(1):
        c += (~k&k-1).bit_length()
        if c >= n:
            return k # Chai Wah Wu, Jul 08 2022

Formula

a(n) = A002034(2^n). For n>1, it appears that a(n+1) = a(n)+2 if n is in A005187. - Benoit Cloitre, Sep 01 2002

G.f.: 1 + 2*(x/(1-x))*Product_{k >= 1} (1+x^(2^k-1)). - Wadim Zudilin, Dec 07 2015

a(n) = 2*A046699(n) for n > 0. - Michel Marcus and M. F. Hasler, Dec 27 2019

a(2^i + r) = 2^i + a(r+1) for 0 <= r <= 2^i-2, and a(2^i + r) = 2^(i+1) for r = 2^i-1. - Kevin Ryde, Aug 06 2022