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,2

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.

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

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A089003 A132118 A221952 * A239826 A246601 A288529

Adjacent sequences: A007840 A007841 A007842 * A007844 A007845 A007846

Keyword

nonn,easy,nice

Author

Bruce Dearden and Jerry Metzger; R. Muller

Status

approved