A296150 Triangle whose n-th row is the integer partition with Heinz number n.

1, 2, 1, 1, 3, 2, 1, 4, 1, 1, 1, 2, 2, 3, 1, 5, 2, 1, 1, 6, 4, 1, 3, 2, 1, 1, 1, 1, 7, 2, 2, 1, 8, 3, 1, 1, 4, 2, 5, 1, 9, 2, 1, 1, 1, 3, 3, 6, 1, 2, 2, 2, 4, 1, 1, 10, 3, 2, 1, 11, 1, 1, 1, 1, 1, 5, 2, 7, 1, 4, 3, 2, 2, 1, 1, 12, 8, 1, 6, 2, 3, 1, 1, 1, 13, 4

Offset

1,2

Comments

Same as A112798 with rows reversed. Row lengths are A001222. Rows sums are A056239.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

Links

Robert Israel, Table of n, a(n) for n = 1..10002 (rows 1 to 3272, flattened)

Example

Sequence of partitions begins: (), (1), (2), (11), (3), (21), (4), (111), (22), (31), (5), (211), (6), (41), (32), (1111), (7), (221).

Maple

f := n -> op(map(numtheory:-pi, sort(map(`$`@op, ifactors(n)[2]), `>`))):
map(f, [$1..100]); # Robert Israel, Feb 09 2018

Mathematica

Table[If[n===1, {}, Join@@Cases[FactorInteger[n]//Reverse, {p_, k_}:>Table[PrimePi[p], {k}]]], {n, 50}]

Crossrefs

Cf. A000041, A000720, A001222, A056239, A063834, A112798, A196545, A215366, A289501, A299200, A299201, A299202, A299203.

Keyword

nonn,tabf,look

Author

Gus Wiseman, Feb 05 2018

Status

approved

A060117 A list of all finite permutations in "PermUnrank3R" ordering. (Inverses of the permutations of A060118.)

1, 2, 1, 1, 3, 2, 3, 1, 2, 3, 2, 1, 2, 3, 1, 1, 2, 4, 3, 2, 1, 4, 3, 1, 4, 2, 3, 4, 1, 2, 3, 4, 2, 1, 3, 2, 4, 1, 3, 1, 4, 3, 2, 4, 1, 3, 2, 1, 3, 4, 2, 3, 1, 4, 2, 3, 4, 1, 2, 4, 3, 1, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4, 3, 2, 1, 3, 4, 2, 1, 3, 2, 4, 1, 2, 3, 4, 1, 1, 2, 3, 5, 4, 2, 1, 3, 5, 4, 1, 3, 2, 5, 4, 3, 1, 2

Offset

0,2

Comments

PermUnrank3R and PermUnrank3L are slight modifications of unrank2 algorithm presented in Myrvold-Ruskey article.

Links

Table of n, a(n) for n=0..104.

W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time, Inform. Process. Lett. 79 (2001), no. 6, 281-284.

Formula

[seq(op(PermUnrank3R(j)), j=0..)]; (Maple code given below)

Example

In this table each row consists of A001563[n] permutations of (n+1) terms; i.e., we have (1/) 2,1/ 1,3,2; 3,1,2; 3,2,1; 2,3,1/ 1,2,4,3; 2,1,4,3;
Append to each an infinite number of fixed terms and we get a list of rearrangements of natural numbers, but with only a finite number of terms permuted:
1/2,3,4,5,6,7,8,9,...
2,1/3,4,5,6,7,8,9,...
1,3,2/4,5,6,7,8,9,...
3,1,2/4,5,6,7,8,9,...
3,2,1/4,5,6,7,8,9,...
2,3,1/4,5,6,7,8,9,...
1,2,4,3/5,6,7,8,9,...
2,1,4,3/5,6,7,8,9,...

Maple

with(group); permul := (a, b) -> mulperms(b, a); PermUnrank3R := proc(r) local n; n := nops(factorial_base(r)); convert(PermUnrank3Raux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end; PermUnrank3Raux := proc(n, r, p) local s; if(0 = r) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Raux(n-1, r-(s*((n-1)!)), permul(p, [[n, n-s]]))); fi; end;

Crossrefs

A060119 = Positions of these permutations in the "canonical list" A055089 (where also the rest of procedures can be found). A060118 gives position of the inverse permutation of each and A065183 positions after Foata transform.

Inversion vectors: A064039.

Cf. A060125, A060128, A060129, A060130, A060131, A060132, A060495.

Keyword

nonn,tabf

Author

Antti Karttunen, Mar 02 2001

Status

approved

A338912 Lesser prime index of the n-th semiprime.

1, 1, 2, 1, 1, 2, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 4, 2, 3, 2, 1, 1, 3, 2, 1, 4, 1, 3, 1, 2, 4, 2, 1, 3, 1, 2, 3, 1, 4, 5, 1, 2, 2, 4, 1, 2, 1, 5, 3, 1, 3, 1, 2, 4, 1, 6, 2, 1, 2, 3, 5, 1, 2, 1, 4, 3, 1, 5, 2, 1, 3, 4, 1, 2, 6, 1, 3, 2, 6, 2, 5, 1, 4, 1, 3, 2, 1

Offset

1,3

Comments

A semiprime is a product of any two prime numbers. A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

Links

Table of n, a(n) for n=1..87.

Formula

a(n) = A000720(A084126(n)).

Example

The semiprimes are:
  2*2, 2*3, 3*3, 2*5, 2*7, 3*5, 3*7, 2*11, 5*5, 2*13, ...
so the lesser prime factors are:
  2, 2, 3, 2, 2, 3, 3, 2, 5, 2, ...
with indices:
  1, 1, 2, 1, 1, 2, 2, 1, 3, 1, ...

Mathematica

Table[Min[PrimePi/@First/@FactorInteger[n]], {n, Select[Range[100], PrimeOmega[#]==2&]}]

Crossrefs

A084126 is the lesser prime factor (not index).

A084127 is the greater factor, with index A338913.

A115392 lists positions of ones.

A128301 lists positions of first appearances of each positive integer.

A270650 is the squarefree case, with greater part A270652.

A338898 has this as first column.

A001221 counts distinct prime indices.

A001222 counts prime indices.

A001358 lists semiprimes, with odds A046315 and evens A100484.

A006881 lists squarefree semiprimes, with odds A046388 and evens A100484.

A087794/A176504/A176506 are product/sum/difference of semiprime indices.

A338910/A338911 list products of pairs of odd/even-indexed primes.

Cf. A037143, A056239, A065516, A112798, A289182, A320732, A320892, A338900, A338904, A338909.

Keyword

nonn

Author

Gus Wiseman, Nov 20 2020

Status

approved

A270650 Min(i, j), where p(i)*p(j) is the n-th term of A006881.

1, 1, 1, 2, 2, 1, 1, 2, 1, 3, 1, 2, 1, 2, 3, 2, 1, 1, 3, 2, 1, 4, 1, 3, 1, 2, 4, 2, 1, 3, 1, 2, 3, 1, 4, 1, 2, 2, 4, 1, 2, 1, 5, 3, 1, 3, 1, 2, 4, 1, 2, 1, 2, 3, 5, 1, 2, 1, 4, 3, 1, 5, 2, 1, 3, 4, 1, 2, 6, 1, 3, 2, 6, 2, 5, 1, 4, 1, 3, 2, 1, 1, 4, 2, 3, 1

Offset

1,4

Links

Clark Kimberling, Table of n, a(n) for n = 1..1000

Example

A006881 = (6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, ... ), the increasing sequence of all products of distinct primes.  The first 4 factorizations are 2*3, 2*5, 2*7, 3*5, so that (a(1), a(2), a(3), a(4)) = (1,1,1,2).

Mathematica

mx = 350; t = Sort@Flatten@Table[Prime[n]*Prime[m], {n, Log[2, mx/3]}, {m, n + 1, PrimePi[mx/Prime[n]]}]; (* A006881, Robert G. Wilson v, Feb 07 2012 *)
u = Table[FactorInteger[t[[k]]][[1]], {k, 1, Length[t]}];
u1 = Table[u[[k]][[1]], {k, 1, Length[t]}]  (* A096916 *)
PrimePi[u1]  (* A270650 *)
v = Table[FactorInteger[t[[k]]][[2]], {k, 1, Length[t]}];
v1 = Table[v[[k]][[1]], {k, 1, Length[t]}]  (* A070647 *)
PrimePi[v1]  (* A270652 *)
d = v1 - u1  (* A176881 *)
Map[PrimePi[FactorInteger[#][[1, 1]]] &, Select[Range@ 240, And[SquareFreeQ@ #, PrimeOmega@ # == 2] &]] (* Michael De Vlieger, Apr 25 2016 *)

Crossrefs

Cf. A000040, A006881, A096916, A070647, A270652, A270003.

Keyword

nonn,easy

Author

Clark Kimberling, Apr 25 2016

Status

approved

A025428 Number of partitions of n into 4 nonzero squares.

0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 3, 0, 1, 2, 0, 1, 2, 1, 2, 2, 1, 2, 1, 0, 3, 2, 1, 2, 1, 2, 1, 2, 2, 1, 4, 1, 2, 3, 0, 2, 4, 1, 3, 2, 1, 4, 1, 1, 3, 3, 2, 2, 4, 2, 1, 3, 2, 3, 4, 2, 3, 3, 1, 2, 5, 2, 4, 3, 2, 4, 1, 1, 6, 4, 3, 4, 2, 3, 0, 4, 4, 3, 5, 1, 5, 5, 1, 4, 5, 2

Offset

0,29

Comments

Records occur at n= 4, 28, 52, 82, 90, 130, 162, 198, 202, 210,.... - R. J. Mathar, Sep 15 2015

Links

T. D. Noe, Table of n, a(n) for n = 0..10000

Index entries for sequences related to sums of squares

Formula

For n>0, a(n) = ( A063730(n) + 6*A213024(n) + 3*A063725(n/2) + 8*A092573(n) + 6*A010052(n/4) ) / 24. - Max Alekseyev, Sep 30 2012

a(n) = ( A000118(n) - 4*A005875(n) - 6*A004018(n) - 12*A000122(n) - 15*A000007(n) + 12*A014455(n) - 24*A033715(n) - 12*A000122(n/2) + 12*A004018(n/2) + 32*A033716(n) - 32*A000122(n/3) + 48*A000122(n/4) ) / 384. - Max Alekseyev, Sep 30 2012

a(n) = [x^n y^4] Product_{k>=1} 1/(1 - y*x^(k^2)). - Ilya Gutkovskiy, Apr 19 2019

a(n) = Sum_{k=1..floor(n/4)} Sum_{j=k..floor((n-k)/3)} Sum_{i=j..floor((n-j-k)/2)} A010052(i) * A010052(j) * A010052(k) * A010052(n-i-j-k). - Wesley Ivan Hurt, Apr 19 2019

Maple

A025428 := proc(n)
    local a, i, j, k, lsq ;
    a := 0 ;
    for i from 1 do
        if 4*i^2 > n then
            return a;
        end if;
        for j from i do
            if i^2+3*j^2 > n then
                break;
            end if;
            for k from j do
                if i^2+j^2+2*k^2 > n then
                    break;
                end if;
                lsq := n-i^2-j^2-k^2 ;
                if lsq >= k^2 and issqr(lsq) then
                    a := a+1 ;
                end if;
            end do:
        end do:
    end do:
end proc:
seq(A025428(n), n=1..40) ; # R. J. Mathar, Jun 15 2018
# second Maple program:
b:= proc(n, i, t) option remember; `if`(n=0, `if`(t=0, 1, 0),
     `if`(i<1 or t<1, 0, b(n, i-1, t)+`if`(i^2>n, 0, b(n-i^2, i, t-1))))
    end:
a:= n-> b(n, isqrt(n), 4):
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 14 2019

Mathematica

nn = 100; lim = Sqrt[nn]; t = Table[0, {nn}]; Do[n = a^2 + b^2 + c^2 + d^2; If[n <= nn, t[[n]]++], {a, lim}, {b, a, lim}, {c, b, lim}, {d, c, lim}]; t (* T. D. Noe, Sep 28 2012 *)
f[n_] := Length@ IntegerPartitions[n, {4}, Range[ Floor[ Sqrt[n - 1]]]^2]; Array[f, 105] (* Robert G. Wilson v, Sep 28 2012 *)

Prog

(PARI) A025428(n)=sum(a=1, n, sum(b=1, a, sum(c=1, b, sum(d=1, c, a^2+b^2+c^2+d^2==n))))
(PARI) A025428(n)=sum(a=1, sqrtint(max(n-3, 0)), sum(b=1, min(sqrtint(n-a^2-2), a), sum(c=1, min(sqrtint(n-a^2-b^2-1), b), issquare(n-a^2-b^2-c^2, &d) & d <= c )))
(PARI) A025428(n)=sum(a=sqrtint(max(n, 4)\4), sqrtint(max(n-3, 0)), sum(b=sqrtint((n-a^2)\3-1)+1, min(sqrtint(n-a^2-2), a), sum(c=sqrtint((t=n-a^2-b^2)\2-1)+1, min(sqrtint(t-1), b), issquare(t-c^2) ))) \\ - M. F. Hasler, Sep 17 2012
for(n=1, 100, print1(A025428(n), ", "))
(PARI) T(n)={a=matrix(n, 4, i, j, 0); for(d=1, sqrtint(n), forstep(i=n, d*d+1, -1, for(j=2, 4, a[i, j]+=sum(k=1, j, if(k<j&&i-k*d*d>0, a[i-k*d*d, j-k], if(k==j&&i-k*d*d==0, 1))))); a[d*d, 1]=1); for(i=1, n, print(i" "a[i, 4]))} /* Robert Gerbicz, Sep 28 2012 */

Crossrefs

Cf. A000414, A000534, A025357-A025375, A216374, A025416 (greedy inverse).

Column k=4 of A243148.

Keyword

nonn,easy

Author

David W. Wilson

Extensions

Values of a(0..10^4) double-checked by M. F. Hasler, Sep 17 2012

Status

approved

A033150 Decimal expansion of Niven's constant.

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

Offset

1,2

Comments

This constant is the average value of A051903. - Charles R Greathouse IV, Oct 30 2012

There are no 9's in the first 50 digits after the decimal point. Then, suddenly, it goes 909999. - Bobby Jacobs, Aug 13 2017

Named after the Canadian-American mathematician Ivan Morton Niven (1915 - 1999). - Amiram Eldar, Aug 19 2020

References

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, pp. 112-115.

Links

Table of n, a(n) for n=1..102.

C. W. Anderson, Problem 6015, The American Mathematical Monthly, Vol. 82, No. 2 (1975), pp. 183-184, T. Salat, Prime Decomposition of Integers, solution to Problem 6015, ibid., Vol. 83, No. 10 (1976), p. 820.

Ivan Niven, Averages of Exponents in Factoring Integers, Proc. Amer. Math. Soc., Vol. 22, No. 2 (1969), pp. 356-360.

Simon Plouffe, The Niven constant to 256 digits.

Kaneenika Sinha, Average orders of certain arithmetical functions, Journal of the Ramanujan Mathematical Society, Vol. 21, No. 3 (2006), pp. 267-277.

Eric Weisstein's World of Mathematics, Niven's Constant.

Wikipedia, Niven's constant.

Formula

Equals 1 + Sum_{j>=2} 1-(1/zeta(j)).

Equals 1 - Sum_{k>=2} mu(k)/(k*(k-1)), where mu is the Möbius function (A008683) (Anderson, 1975; Sinha, 2006). - Amiram Eldar, Aug 19 2020

Example

1.7052111401...

Mathematica

rd[n_] := rd[n] = RealDigits[ N[1 + Sum[1 - 1/Zeta[j], {j, 2, 2^n}] , 105]][[1]]; rd[n = 4]; While[rd[n] =!= rd[n-1], n++]; rd[n] (* Jean-François Alcover, Oct 25 2012 *)

Prog

(PARI) 1+suminf(j=2, 1-1/zeta(j)) \\ Charles R Greathouse IV, Aug 13 2017

Crossrefs

Cf. A008683, A033151, A033152, A033153, A033154.

Keyword

nonn,cons

Author

Eric W. Weisstein

Extensions

Offset corrected by Oleg Marichev (oleg(AT)wolfram.com), Jan 28 2008

Status

approved

A155115 Decimal expansion of log_20 (19).

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

Offset

0,1

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Index entries for transcendental numbers

Example

.98287787769275567974645694886429924059807154950413218628850...

Mathematica

RealDigits[Log[20, 19], 10, 100][[1]] (* Vincenzo Librandi, Sep 05 2013 *)

Crossrefs

Cf. decimal expansion of log_20(m): A152821 (m=2), A153035 (m=3), A153124 (m=4), A153454 (m=5), A153610 (m=6), A153630 (m=7), A153872 (m=8), A154019 (m=9), A154170 (m=10), A154191 (m=11), A154212 (m=12), A154433 (m=13), A154492 (m=14), A154705 (m=15), A154838 (m=16), A154900 (m=17), A154976 (m=18), this sequence, A155687 (m=21), A155789 (m=22), A155907 (m=23), A156015 (m=24).

Keyword

nonn,cons

Author

N. J. A. Sloane, Oct 30 2009

Status

approved

A135303 a(n) = phi(2*n+1)/(2*A003558(n)), where phi = A000010.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 1, 3, 4, 1, 1, 1, 4, 1, 1, 1, 1, 1, 4, 1, 4, 3, 3, 1, 2, 2, 1, 1, 2, 1, 3, 1, 4, 1, 3, 2, 1, 2, 1, 9, 6, 1, 3, 1, 2, 1, 1, 1, 4, 1, 1, 5, 2, 3, 3, 1, 2, 1, 2, 1, 1, 6, 1, 1, 2

Offset

1,8

Comments

The Froemke-Grossman 1988 reference is the earliest I have seen. a(n) is the charm bracelet function b(2,2*n+1) in their notation. - N. J. A. Sloane, Feb 28 2023

This sequence is called the "coach numbers" ("c(2*n+1)"), and was studied by J. Pedersen, Byron Walden, Victor Quintanar-Zilinskas and Linda Velarde of Santa Clara University. Coach Theorem: Let b = 2*n+1 > 1 and let phi(b) be the Euler totient function. Let Sigma(b) be the complete symbol of b, let c be the number of coaches in Sigma(b), and let k = Sum_{i=1..r} k(i). Then phi(b) = 2 * c * k [Hilton & Pedersen, p. 262]. The complete symbols for b = 17 and 43 are shown in the examples. - Gary W. Adamson, Aug 15 2012

Conjecture relating to primes with more than one coach: The combined set of integers in the top rows of all coaches of these primes is composed of a permutation of the first q odd integers, where prime p = (4q-1) or (4q+1), (q > 0). Example: As shown for 17, this prime has two coaches with the top rows [1] and [3, 7, 5]. 43 has three coaches with q = 11. The top rows are [1, 21, 11], [3, 5, 19], [7, 9, 17, 13, 15]. The comment of Sep 08 2012 in A216371 applies to primes with one coach, in which case "all coaches" is reduced to one and the set of q odd integers is in the top row of the coach. - Gary W. Adamson, Sep 10 2012

Conjecture [Carl Schick]: If 2*n+1 is prime, then these are the number of distinct cycles of f(k) = |(2*n+1) - 2*k| beginning at an odd number 0 < k < 2*n. - Jonathan Skowera, Aug 03 2013 [See also the Brändli and Beyne link, eq. (2). - Wolfdieter Lang, Feb 08 2020]

From Gary W. Adamson, Oct 04 2019: (Start)

Conjecture of Aug 03 2013 proved by Jean Pedersen. By way of example, take A003558(5) = 11, such that

2^5 == -1 (mod 11). Then Pedersen on p. 98 has:

11 - 1 = 2^1 * 5 (pick "1", odd, the putative seed number)

11 - 5 = 2^1 * 3 (then subtract 3 in the next row)

11 - 3 = 2^3 * 1 (cycle ends). Then Pedersen constructs the "coach" (p. 98) for N= 11: [1, 5, 3]

.......... [1, 1, 3]. The top row represents the angles on the tape used to construct an 11-gon at the operative crease lines beginning with Pi/11. (extract the (1,5,3) column). Then extract the exponents of 2: (1,1,3); which are the bottom row terms. The final result is that at successive creases on the tape are at angles of j*Pi/11, j = (1,5,3); alternatively at the top of the tape, then the bottom. The code U(1), D(1), U(3) is understood to be those numbers of bisections at each vertex. The total numbers of bisections = 5 = (1 + 1 + 3), shown to be the entry for N = 11 in A003558. (End)

References

Froemke, Jon, and Jerrold W. Grossman. "An algebraic approach to some number-theoretic problems arising from paper-folding regular polygons." The American mathematical monthly 95.4 (1988): 289-307. See Appendix.

Peter Hilton & Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics; Cambridge University Press, 2010, pages 260-264.

Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6). Tables 3.1 to 3.10, for odd p = 3..113, pp. 158-166.

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.

Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.

V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, [in Russian], Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53.

V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, Probl Inf Transm 43, 199-212 (2007).

Formula

a(n) = "c", a Coach number; = A000010(n)/(2*A003558(n-1)/2)); or phi(2*n+1) = 2 * c * k, with c = Coach numbers, k = A003558.

Example

Refer to A003558 for the J. Pedersen definition of a Coach. a(8) for b = 17 = 2 since 17 has two possible Coaches:
17: [1] and [3, 7, 5]
    [4]     [1, 1, 2];
where sum of the bottom row terms = k = 4 = A003558(8). For b = 43, a(21) = 3 since there are three possible coaches for 43:
43: [1, 21, 11]  [3, 5, 19]  [7, 9, 17, 13, 15]
    [1,  1,  5], [3, 1,  3], [2, 1,  1,  1,  2],
where k = sum of terms in bottom rows of all possible coaches = 7 = A003558(21). For the coach with a "1" in the top row, the numbers of terms in the rows ("j" in A003558), = A179480(22) = 3. Note that the parity of numbers of terms in the bottom coach rows is the same.
From Gary W. Adamson, Aug 24 2019: (Start)
An alternative to the coach method of Pedersen and Hilton involves the doubling sequence, mod n; (43 in this case). The top row begins (1, 2, 4, 8, 16, ...) but the next number is 11, not 32. 32 == -11 (mod 43). We pick the least (in absolute value) of the two candidates (11 and 32): 11. The top row ends when the rightmost term is (n-1)/2 = 21. In subsequent rows the leftmost term is the least odd number not previously used, in this case 3. Continue with the doubling sequence and stop when the next row produces a term already used.
"20" ends row 2 since (2 * 20) = 40 == -3 (mod 43). 3 has been used so that row ends and our next row begins with the next unused odd term, a 7. That row ends with 18 since 2 * 18 = 36 == -7 (mod 43).
The entire set is complete when every term (1 through (n-1)/2) is present without duplication. In this method, k is likewise 7 but is represented by the numbers of terms in the top row. Pedersen's [1, 21, 11] appears as the only odd terms of the top row. [3,  5, 19] appears as the odd terms of the middle row, and [7, 9, 17, 13, 15] are the only odd terms of the bottom row. The three completed rows are:
  [1,  2,  4,  8, 16, 11, 21;
   3,  6, 12, 19,  5, 10, 20;
   7, 14, 15, 13, 17,  9, 18]
  It appears that the numbers of rows is equal to Pedersen's
  number of coaches. Another example is the complete system of coaches shown on p. 261 of (Hilton and Pedersen):
  31: [1, 15], [3, 7], [5, 13, 9, 11]
      [1,  4], [2, 3], [1,  1, 1,  2]
  The alternative system, called an r-t table in A065941, is
     [1,  2,  4, 8, 15;
      3,  6, 12, 7, 14;
      5, 10, 11, 9, 13]
  The odd terms of the top row (1, 15) appear in the leftmost coach. The odd terms (3, 7) appear in the middle coach, and (5, 11, 9, 13) are shown in the rightmost coach. (End)
Pedersen's coaches can be derived from the alternative system, doubling (mod N) since her coaches are simply another version: (repeated bisections (mod N)). First write out the doubling terms (mod N). Say N = 23: 1, 2, 4, 8, 7, 9, 5, 10, 3, 6, 11, representing the trajectory of terms 2*cos(j*Pi/23), using (x^2-2); j = 1, 2, 4, .... Begin with ("1"), then jump to the next odd term (11), then to each odd term in succession going left, getting: 23: (1, 11, 3, 5, 9, 7); the top row in Pedersen's coach. ....(1, 2, 2, 1, 1, 4) is the bottom row for 23 as shown on p. 105. Those terms are the numbers of term jumps in the previous operation; for example (1 to 11) = 1, (11 to 3) = 2, (3 to 5) = 2; and so on.  Note that the number of terms in the doubling trajectory (11) matches the sum of terms in the bottom row of the coach, satisfying 2^11 == 1 (mod 23). - Gary W. Adamson, Oct 23 2019

Maple

A135303 := proc(n)
    numtheory[phi](2*n+1)/2/A003558(n) ;
end proc:
seq(A135303(n), n=1..40) ; # R. J. Mathar, Dec 01 2014

Mathematica

Array[EulerPhi[#2]/(2 If[#2 > 1 && GCD[#1, #2] == 1, Min[MultiplicativeOrder[#1, #2, {-1, 1}]], 0]) & @@ {2, 2 # + 1} &, 105] (* Michael De Vlieger, Oct 25 2019 *)

Prog

(PARI) isok8(m, n) = my(md = Mod(2, 2*n+1)^m); (md==1) || (md==-1);
A003558(n) = my(m=1); while(!isok8(m, n) , m++); m;
a(n) = eulerphi(2*n+1)/(2*A003558(n)); \\ Michel Marcus, Jun 11 2020

Crossrefs

Cf. A003558, A179480.

Cf. A216371 (odd primes with one coach).

Keyword

nonn

Author

N. J. A. Sloane, Dec 05 2007

Extensions

Title changed by Wolfdieter Lang and M. F. Hasler, Feb 20 2020

Status

approved

A050412 Riesel problem: start with n; repeatedly double and add 1 until reaching a prime. Sequence gives number of steps to reach a prime or 0 if no prime is ever reached.

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 4, 1, 1, 2, 2, 1, 2, 1, 1, 4, 1, 3, 2, 1, 3, 4, 1, 1, 2, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 7, 24, 1, 3, 4, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 12, 2, 3, 4, 2, 1, 4, 1, 5, 2, 1, 1, 2, 4, 7, 2552, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 5, 6, 1, 23, 4, 1, 1, 2, 3, 3, 2, 1, 1, 4, 1, 1

Offset

1,4

Comments

a(n) is the smallest m >= 1 such that (n+1)*2^m - 1 is prime (or 0 if no such prime exists).

It is conjectured that n = 509203 is the smallest Riesel number, i.e., n*2^k -1 is composite for every k>0. - Robert G. Wilson v, Mar 01 2015

Links

Robert G. Wilson v, Table of n, a(n) for n = 1..2291 (first 657 terms from T. D. Noe)

Ray Ballinger and Wilfrid Keller, The Riesel Problem: Definition and Status, Proth Search Page.

Formula

If a(n) = k with k>1, then a(2n+1) = k-1. - Robert G. Wilson v, Mar 01 2015

If a(n) = 0, then a(2n+1) is also 0. Conjecture: If a(n) = 1, then a(2n+1) is not 0. - Jeppe Stig Nielsen, Feb 12 2023 -

Example

For n=4; the smallest m>=1 such that (4+1)*2^m-1 is prime is m=2: 5*2^2-1=19 (prime). - Jaroslav Krizek, Feb 13 2011

Maple

A050412 := proc(n)
    local twox1, k ;
    twox1 := 2*n+1 ;
    k := 1;
    while not isprime(twox1) do
        twox1 := 2*twox1+1 ;
        k := k+1 ;
    end do:
    return k;
end proc: # R. J. Mathar, Jul 23 2015

Mathematica

a[n_] := Block[{s=n, c=1}, While[ ! PrimeQ[2*s+1], s = 2*s+1; c++]; c]; Table[ a[n], {n, 1, 99} ] (* Jean-François Alcover, Feb 06 2012, after Pari *)
a[n_] := Block[{k = 1}, While[ !PrimeQ[2^k (n + 1) - 1], k++]; Array[a, 100] (* Robert G. Wilson v, Feb 14 2015 *)

Prog

(PARI) a(n)=if(n<0, 0, s=n; c=1; while(isprime(2*s+1)==0, s=2*s+1; c++); c)

Crossrefs

Cf. A051914, A052333 (primes reached), A052334, A052339, A052340, A050413, A076337, A078680, A101036.

Cf. A040081 (allows m >= 0).

Keyword

nonn,nice,easy

Author

Robert G. Wilson v, Dec 22 1999

Extensions

More terms from Christian G. Bower, Dec 23 1999

Second definition corrected by Jaroslav Krizek, Feb 13 2011

Status

approved

A046067 Smallest m such that (2n-1)2^m+1 is prime, or -1 if no such value exists.

0, 1, 1, 2, 1, 1, 2, 1, 3, 6, 1, 1, 2, 2, 1, 8, 1, 1, 2, 1, 1, 2, 2, 583, 2, 1, 1, 4, 2, 5, 4, 1, 1, 2, 1, 3, 2, 1, 3, 2, 1, 1, 4, 2, 1, 8, 2, 1, 2, 1, 3, 16, 1, 3, 6, 1, 1, 2, 3, 1, 8, 6, 1, 2, 3, 1, 4, 1, 3, 2, 1, 53, 6, 8, 3, 4, 1, 1, 8, 6, 3, 2, 1, 7, 2, 8, 1, 2, 2, 1, 4, 1, 3, 6, 1, 1, 2, 4, 15, 2

Offset

1,4

Comments

There exist odd integers 2k-1 such that (2k-1)2^n+1 is always composite.

The smallest known example is 78557. Therefore a(39279) = -1.

For the corresponding primes see A057025(n-1), n >= 1, where a 0 will show up if a(n) = -1. - Wolfdieter Lang, Feb 07 2013.

Jaeschke shows that every positive integer appears infinitely often. - Jeppe Stig Nielsen, Jul 06 2020

References

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 357-359, 1996.

Links

T. D. Noe, Table of n, a(n) for n = 1..5000 (with help from the Sierpiński problem website; typo in a(3707)=1 corrected by Jeppe Stig Nielsen)

Ray Ballinger and Wilfrid Keller, Sierpiński Problem

John R. Cowles and Ruben Gamboa, Verifying Sierpiński and Riesel Numbers in ACL2, arXiv preprint arXiv:1110.4671 [cs.DM], 2011.

G. Jaeschke, On the Smallest k Such that All k*2^N + 1 are Composite, Mathematics of Computation, Vol. 40, No. 161 (Jan., 1983), pp. 381-384.

Seventeen or Bust, A Distributed Attack on the Sierpiński Problem

W. Sierpiński, Sur un problème concernant les nombres k*2^n+1, Elem. d. Math. 15, pp. 73-74, 1960.

Eric Weisstein's World of Mathematics, Riesel Number.

Eric Weisstein's World of Mathematics, Sierpiński Number of the Second Kind.

Mathematica

max = 10000 (* this maximum value of m is sufficient up to n = 1000 *); a[n_] := For[m = 1, m <= max, m++, If[PrimeQ[(2n - 1)*2^m + 1], Return[m]]] /. Null -> -1; a[1] = 0; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jun 08 2012 *)

Crossrefs

Cf. A046068.

Bisection of A040076. Cf. A033809.

Cf. A057192, A057025.

Keyword

sign

Author

Eric W. Weisstein

Status

approved