A001146 -id:A001146 - cp's OEIS frontend

A058220 Ultra-useful primes: smallest k such that 2^(2^n) - k is prime.

1, 3, 5, 15, 5, 59, 159, 189, 569, 105, 1557, 2549, 2439, 13797, 25353, 5627, 24317, 231425, 164073

Offset: 1

Warren D. Smith, Nov 30 2000

2^(2^16) - 5627 was found by Joel Levy in Feb 2004. - Donovan Johnson, Sep 13 2008

Corresponding numbers to entries a(1) to a(12) are proven primes, higher terms are probable primes. - Matthias Baur, Mar 17 2020

			For n = 3, we see that 2^(2^3) = 2^8 = 256, which is clearly not prime.
256 - 1 = 255 = 3 * 5 * 17, so a(3) is not 1.
256 - 2 = 254 = 2 * 127, so a(3) is not 2 either.
256 - 3 = 253 = 11 * 23, so a(3) is not 3 either.
256 - 5 = 251, which is prime, so a(3) = 5.

Rosetta Code, Ultra-useful primes.

Cf. A001146, A013603, A058221.

ultraUseful[n_] := Module[{x = 2^(2^n)}, x - NextPrime[x, -1]]; Array[ultraUseful, 17] (* Harvey P. Dale, Jun 04 2011 *)

a(n) = A013603(2^n). - Jinyuan Wang, Jun 06 2020

a(16)-a(17) from Donovan Johnson, Sep 13 2008
a(18) from Matthias Baur, Mar 17 2020
a(19) from Matthias Baur, Apr 04 2020

A326969 Number of sets of subsets of {1..n} whose dual is a weak antichain.

Original entry on oeis.org

2, 4, 12, 112, 38892

Offset: 0

Gus Wiseman, Aug 10 2019

The dual of a set of subsets has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

			The a(0) = 2 through a(2) = 12 sets of subsets:
  {}    {}        {}
  {{}}  {{}}      {{}}
        {{1}}     {{1}}
        {{},{1}}  {{2}}
                  {{1,2}}
                  {{},{1}}
                  {{},{2}}
                  {{1},{2}}
                  {{},{1,2}}
                  {{},{1},{2}}
                  {{1},{2},{1,2}}
                  {{},{1},{2},{1,2}}

Sets of subsets whose dual is strict are A326941.
The BII-numbers of set-systems whose dual is a weak antichain are A326966.
Sets of subsets whose dual is a (strict) antichain are A326967.
The case without empty edges is A326968.
Cf. A001146, A059052, A326951, A326970, A326971, A326975, A326978.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n]]],stableQ[dual[#],SubsetQ]&]],{n,0,3}]

a(n) = 2 * A326968(n).

a(n) = 2 * Sum_{k = 0..n} binomial(n, k) * A326970(k).

A369605 Irregular triangle read by rows: T(n,k) is the number of inequivalent connected induced k-vertex subgraphs of the hypercube graph of dimension n >= 0, 1 <= k <= 2^n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 5, 11, 19, 36, 37, 41, 24, 18, 6, 4, 1, 1, 1, 1, 1, 3, 5, 17, 44, 158, 493, 1628, 4670, 12266, 27043, 51018, 79042, 103179, 112219, 105232, 84045, 59021, 35533, 19114, 8769, 3716, 1311, 468, 130, 47, 10, 5, 1, 1

Offset: 0

Pontus von Brömssen, Jan 27 2024

Two subgraphs are equivalent if there is an automorphism of the hypercube graph that takes one to the other.
Two isomorphic subgraphs may both be counted. For example, the path with 5 vertices is an induced subgraph of the 4-dimensional hypercube in two inequivalent ways: one that is contained in a 3-dimensional subcube and one that is not. This implies that T(4,5) > A369997(4,5). (In A369997, the subgraphs are counted up to isomorphism.)
Also, number of free k-celled polycubes in n dimensions, whose width in any coordinate direction is at most 2.
Also, number of k-celled polyominoes whose cells are subsets of the (n-1)-dimensional facets of the n-dimensional cross-polytope (or orthoplex). (See A049540.)
A039754 is the corresponding sequence for not necessarily connected subgraphs.

			Triangle begins:
  1;
  1, 1;
  1, 1, 1, 1;
  1, 1, 1, 3, 2,  3,  1,  1;
  1, 1, 1, 3, 5, 11, 19, 36, 37, 41, 24, 18, 6, 4, 1, 1;
  ...
There are T(3,4) = 3 inequivalent connected induced 4-vertex subgraphs of the 3-cube: four vertices of a 2-dimensional face or three vertices of a face together with a vertex from the opposite face, adjacent to either of two inequivalent vertices from the first face.

Cf. A049540 (main diagonal), A333333 (edge-induced subgraphs).
Different ways of counting induced subgraphs in the hypercube graph (totals or by number of vertices):
            \   Subgraphs   |       All       |   Connected
  Symmetries \              |                 |
  --------------------------+-----------------+----------------
  None                      | A001146/ N/A    | A290758/A369999
  Automorphisms of the cube | A000616/A039754 | A369606/A369605
  Isomorphism               | A369996/A369995 | A369998/A369997
  (The N/A entry corresponds to rows 2^n of Pascal's triangle; A345135 comes close.)

T(n,k) = A049540(k) for k <= n+1.

T(n,k) = A039754(n,k) for k > 2^n-n.

Row 5 from Pontus von Brömssen, May 14 2025

A048707 Numerators of ratios converging to Thue-Morse constant.

Original entry on oeis.org

0, 1, 6, 105, 27030, 1771476585, 7608434000728254870, 140350834813144189858090274002849666665, 47758914269546354982683078068829456704164423862093743397580034411621752859030

Offset: 0

Antti Karttunen, Mar 09 1999

Also interpret each iteration of the construction of the Thue-Morse constant as a binary number converted to a decimal number. Thus (0_b, 01_b, 0110_b, 01101001_b ...) gives the present sequence in decimal. - Robert G. Wilson v, Sep 22 2006

a(n) corresponds to the binary value of the truth-table for the xor operator with n-arguments. - Joe Riel (joer(AT)san.rr.com), Jan 31 2010

Ariel S Koiman, Table of n, a(n) for n = 0..11 (shortened by _N. J. A. Sloane_, Jan 13 2019)
Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 122 (Schroeppel, Gosper)
Eric Weisstein's World of Mathematics, Thue-Morse Sequence

The denominators are given by A001146. Consists of every 2^n-th term of A019300. Cf. A048708 (same sequence in hexadecimal) and A014571, A010060, A014572.

Cf. A080814, A080815, A133468.

Table[ FromDigits[ Nest[ Flatten[ #1 /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, n], 2], {n, 0, 8}] (* Robert G. Wilson v, Sep 22 2006 *)

;returns all but the last element of a list
(define rdc(lambda(x)(if(null? (cdr x))'()(cons (car x) (rdc (cdr x))))))
;gets the two's complement of a given bit
(define twosComplement (lambda (x)(if (eq? x #\0) "1" "0" )))
;gets the two's complement of a string
(define complementOfCurrent (lambda (x y z)(if (eq? (string-length y) z) y (complementOfCurrent (list->string (cdr (string->list x))) (string-append y (twosComplement (string-ref x 0))) z))))
;concatenates the two's complement of a string onto the current string, giving the next element in the TM sequence
(define concatenateComplement (lambda (x i)(if(zero? i) x (concatenateComplement(string-append x (complementOfCurrent x "" (string-length x)))(- i 1)))))
;generates the TM sequence of length 2^x
(define generateThue (lambda (x)(concatenateComplement "0" x)))
;if a bit is 1, get 2^i, where i is the index of that bit from right-left
(define F (lambda (c i)(if (eq? c #\1) (expt 2 i) 0)))
;gathers the sum of 2^index for all indices corresponding to a 1
(define fn (lambda (x sum i stop)(if (eq? i stop) sum (fn (list->string (rdc (string->list x))) (+ sum (F (string-ref x (-(string-length x) 1)) i)) (+ i 1)stop))))
(define f (lambda (x)(fn (generateThue x) 0 0 (string-length (generateThue x)))))
;format: (f x)
;example: (f 10)
;by Ariel S Koiman, Apr 23 2013

a(0) = 0, a(n) = (a(n-1)+1)*((2^(2^(n-1)))-1).

A220294 a(n) = 1 - 2^(2^n) + 2^(2^(n+1)).

Original entry on oeis.org

3, 13, 241, 65281, 4294901761, 18446744069414584321, 340282366920938463444927863358058659841, 115792089237316195423570985008687907852929702298719625575994209400481361428481

Offset: 0

Michael Somos, Dec 10 2012

nonn

An infinite coprime sequence defined by recursion.

Cf. A001146, A002061, A002716, A087046, A111403, A220161, A255770, A255771, A255772.

[1 - 2^(2^n) + 2^(2^(n+1)): n in [0..10]]; // G. C. Greubel, Aug 10 2018

Table[4^(2^m) - 2^(2^m) + 1, {m, 0, 7}] (* Michael De Vlieger, Aug 02 2016 *)

A220294(n):=1 - 2^(2^n) + 2^(2^(n+1))$ makelist(A220294(n),n,0,10); /* Martin Ettl, Dec 10 2012 */

{a(n) = if( n<0, 0, 1 - 2^(2^n) + 2^(2^(n+1)))};

A220161(n+1) = a(n) * A220161(n).
a(n+1) = 1 + (a(n) - 1) * (A220161(n) - 1).
a(n) = A002716(2*n) = 1 + A087046(n+2) = 1 + A111403(n).
a(n) = A002061(A001146(n)). - Pontus von Brömssen, Aug 31 2021

A247219 Positive numbers m such that m^2 - 1 divides 2^m - 1.

Original entry on oeis.org

2, 4, 16, 36, 256, 456, 1296, 2556, 4356, 6480, 8008, 11952, 26320, 44100, 47520, 47880, 49680, 57240, 65536, 74448, 84420, 97812, 141156, 157080, 165600, 225456, 278496, 310590, 333432, 365940, 403900, 419710, 476736, 557040, 560736, 576720, 647088, 1011960, 1033056, 1204560, 1206180

Offset: 1

Juri-Stepan Gerasimov, Nov 26 2014

nonn

Contains all numbers of the form m = A001146(k) = 2^2^k, k >= 0; and those with k > 1 seem to form the intersection with A247165. - M. F. Hasler, Jul 25 2015

			2 is in this sequence because 2^2 - 1 = 3 divides 2^2 - 1 = 3.

Chai Wah Wu, Table of n, a(n) for n = 1..105

Cf. A081762.

[n: n in [2..122222] | Denominator((2^n - 1)/(n^2 - 1)) eq 1];

Select[Range[10^4], Divisible[2^# - 1, #^2 - 1] &] (* Alonso del Arte, Nov 26 2014 *)
Select[Range[2,121*10^4],PowerMod[2,#,#^2-1]==1&] (* Harvey P. Dale, Sep 08 2021 *)

isok(n) = ((2^n - 1) % (n^2 - 1)) == 0; \\ Michel Marcus, Nov 26 2014

forstep(n=0,1e8,2, Mod(2,n^2-1)^n-1 || print1(n", ")) \\ M. F. Hasler, Jul 25 2015

from gmpy2 import powmod
A247219_list = [n for n in range(2,10**7) if powmod(2,n,n*n-1) == 1]
# Chai Wah Wu, Dec 03 2014

Corrected a(24) by Chai Wah Wu, Dec 03 2014

A256607 Eventual period of 2^(2^k) mod n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 2, 2, 1, 1, 1, 2, 6, 1, 2, 4, 10, 1, 4, 2, 6, 2, 3, 1, 4, 1, 4, 1, 2, 2, 6, 6, 2, 1, 4, 2, 3, 4, 2, 10, 11, 1, 6, 4, 1, 2, 12, 6, 4, 2, 6, 3, 28, 1, 4, 4, 2, 1, 2, 4, 10, 1, 10, 2, 12, 2, 6, 6, 4, 6, 4, 2, 12, 1, 18, 4, 20, 2, 1, 3

Offset: 1

Ivan Neretin, Apr 04 2015

nonn

In other words, eventual period of 2 under the map x -> x^2 mod n.

a(n) is a divisor of A256608(n).

			For n=9 the map acts as follows: 2 -> 4 -> 7 -> 4 -> 7 and so on. This means the eventual period is 2, hence a(9)=2.

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A001146, A007733, A002326.
First differs from A256608 at n=43.
Column 2 of triangle in A279185.

a256607 = a007733 . fromIntegral . a007733
-- Reinhard Zumkeller, Apr 13 2015

a(n) = A007733(A007733(n)).

A063486 a(n) = 2^(2^n) + 5.

Original entry on oeis.org

7, 9, 21, 261, 65541, 4294967301, 18446744073709551621, 340282366920938463463374607431768211461, 115792089237316195423570985008687907853269984665640564039457584007913129639941

Offset: 0

Jason Earls, Jul 28 2001

D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston, MA, 1976, p. 238.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, Example 5.1 on page 153.

Harry J. Smith, Table of n, a(n) for n=0..11
Tigran Hakobyan, On the unboundedness of common divisors of distinct terms of the sequence a(n)=2^2^n+d for d>1, arXiv:1601.04946 [math.NT], 2016.

Cf. A000215, A001146, A130729, A130730.

2^2^Range[0, 10] + 5 (* Paolo Xausa, Apr 17 2024 *)

PARI
```
for(n=0,8,print1(2^(2^n)+5, ", "))
```

{ for (n=0, 11, write("b063486.txt", n, " ", 2^(2^n) + 5) ) } \\ Harry J. Smith, Aug 23 2009

[2**2**n + 5 for n in (0..8)] # Stefano Spezia, Jul 20 2025

A181795 Numbers k such that the number of odd divisors of k is an odd divisor of k, and the number of even divisors of k is an even divisor of k.

Original entry on oeis.org

4, 16, 36, 144, 256, 576, 900, 1764, 2304, 2500, 3600, 4356, 6084, 7056, 8100, 10000, 10404, 12996, 17424, 19044, 22500, 24336, 26244, 30276, 32400, 34596, 36864, 41616, 49284, 51984, 57600, 60516, 65536, 66564, 76176, 79524, 90000

Offset: 1

Matthew Vandermast, Nov 14 2010

nonn

All members are even squares (A016742). Intersection of A049439 and A181794.

Includes all numbers of the form A001146(m)*A036896(n) for m>1.

			a(3)=36 has 3 odd divisors (1, 3, and 9) and 6 even divisors (2, 4, 6, 12, 18, and 36). 3 and 6 are odd and even respectively, and both are divisors of 36.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..96 from Harvey P. Dale)

Subsequence of A000290, A016742, A120351.

See also A033950,A181687. For refactorable members of this sequence, see A120349.

ndQ[n_]:=Module[{d=Divisors[n],od,ev},od=Count[d,?OddQ];ev=Count[ d, ?EvenQ]; ev!=0&&OddQ[od]&&EvenQ[ev]&&Divisible[n,od]&&Divisible[ n, ev]]; Select[Range[100000],ndQ] (* Harvey P. Dale, Feb 24 2016 *)

isok(n) = my(nod = numdiv(n>>valuation(n, 2)), noe = if (n%2, 0, numdiv(n/2))); (nod % 2) && nod && !(n % nod) && !(noe % 2) && noe && !(n % noe); \\ Michel Marcus, Jan 14 2014

More terms from Nathaniel Johnston, Nov 17 2010

A242257 Number of binary words of length n that contain all sixteen 4-bit words as (possibly overlapping) contiguous subwords.

Original entry on oeis.org

256, 1344, 5376, 19028, 61808, 188474, 547350, 1522758, 4083256, 10620590, 26912658, 66671138, 161950112, 386663750, 909204980, 2109158718, 4834062186, 10960141396, 24608994426, 54771900982, 120939714274, 265121486866, 577386711942, 1249925021562, 2691031388142

Offset: 19

Alois P. Heinz, May 09 2014

nonn

The expected wait time to see all sixteen 4-bit words is Sum_{n>=0} (1-a(n)/2^n) ~ 58.632877... (with a(n) = 0 for 0 <= n <= 18).

			a(19) = 256: 0000100110101111000, 0000100111101011000, 0000101001101111000, ..., 1111010110010000111, 1111011000010100111, 1111011001010000111.

Alois P. Heinz, Table of n, a(n) for n = 19..2000
Eric Weisstein's World of Mathematics, Coin Tossing
Wikipedia, Deterministic finite automaton

Cf. A001146, A052944, A242167, A242206, A242323, A243820.

b:=
proc(n, l) option remember; local m; m:= min(l[]);
  `if`(m=5, 2^n, `if`(5-m>n, 0,        b(n-1, [   [2, 3, 4, 5, 5][l[1]],
  [1, 1, 1, 1, 5][l[2]],  [2, 3, 4, 4, 5][l[3]],  [1, 1, 1, 5, 5][l[4]],
  [2, 3, 3, 5, 5][l[5]],  [1, 1, 4, 1, 5][l[6]],  [2, 2, 4, 5, 5][l[7]],
  [1, 3, 1, 3, 5][l[8]],  [1, 3, 4, 5, 5][l[9]],  [2, 2, 2, 2, 5][l[10]],
  [2, 3, 3, 2, 5][l[11]], [1, 1, 4, 5, 5][l[12]], [2, 2, 2, 5, 5][l[13]],
  [1, 3, 4, 1, 5][l[14]], [2, 2, 4, 2, 5][l[15]], [1, 3, 1, 5, 5][l[16]]])+
  b(n-1, [                [1, 1, 1, 1, 5][l[1]],  [2, 3, 4, 5, 5][l[2]],
  [1, 1, 1, 5, 5][l[3]],  [2, 3, 4, 4, 5][l[4]],  [1, 1, 4, 1, 5][l[5]],
  [2, 3, 3, 5, 5][l[6]],  [1, 3, 1, 3, 5][l[7]],  [2, 2, 4, 5, 5][l[8]],
  [2, 2, 2, 2, 5][l[9]],  [1, 3, 4, 5, 5][l[10]], [1, 1, 4, 5, 5][l[11]],
  [2, 3, 3, 2, 5][l[12]], [1, 3, 4, 1, 5][l[13]], [2, 2, 2, 5, 5][l[14]],
  [1, 3, 1, 5, 5][l[15]], [2, 2, 4, 2, 5][l[16]]])))
end:
a:= n-> b(n, [1$16]):
seq(a(n), n=19..40);

cp's OEIS Frontend

A058220 Ultra-useful primes: smallest k such that 2^(2^n) - k is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326969 Number of sets of subsets of {1..n} whose dual is a weak antichain.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A369605 Irregular triangle read by rows: T(n,k) is the number of inequivalent connected induced k-vertex subgraphs of the hypercube graph of dimension n >= 0, 1 <= k <= 2^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A048707 Numerators of ratios converging to Thue-Morse constant.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A220294 a(n) = 1 - 2^(2^n) + 2^(2^(n+1)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Formula

A247219 Positive numbers m such that m^2 - 1 divides 2^m - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Python

Extensions

A256607 Eventual period of 2^(2^k) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell