A249744 -id:A249744 - cp's OEIS frontend

A078898 Number of times the smallest prime factor of n is the smallest prime factor for numbers <= n; a(0)=0, a(1)=1.

0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 6, 1, 7, 3, 8, 1, 9, 1, 10, 4, 11, 1, 12, 2, 13, 5, 14, 1, 15, 1, 16, 6, 17, 3, 18, 1, 19, 7, 20, 1, 21, 1, 22, 8, 23, 1, 24, 2, 25, 9, 26, 1, 27, 4, 28, 10, 29, 1, 30, 1, 31, 11, 32, 5, 33, 1, 34, 12, 35, 1, 36, 1, 37, 13, 38, 3, 39, 1, 40, 14, 41, 1, 42, 6, 43

Offset: 0

Reinhard Zumkeller, Dec 12 2002

nonn

From Antti Karttunen, Dec 06 2014: (Start)
For n >= 2, a(n) tells in which column of the sieve of Eratosthenes (see A083140, A083221) n occurs in. A055396 gives the corresponding row index.
(End)

Harvey P. Dale (terms 1 - 1000) & Antti Karttunen, Table of n, a(n) for n = 0..10000

Cf. A002110, A008683, A008836, A020639, A032742, A054272, A055396, A078899, A078896, A083140, A083221, A243055, A246277, A249738, A249744, A249808, A249809, A249810, A249820, A249818, A250470, A250474, A250477, A250478, A251719, A251724, A251728.

Cf. A001248, A006094, A038110, A038111, A090076.

import Data.IntMap (empty, findWithDefault, insert)
a078898 n = a078898_list !! n
a078898_list = 0 : 1 : f empty 2 where
   f m x = y : f (insert p y m) (x + 1) where
           y = findWithDefault 0 p m + 1
           p = a020639 x
-- Reinhard Zumkeller, Apr 06 2015

N:= 1000: # to get a(0) to a(N)
Primes:= select(isprime, [2,seq(2*i+1,i=1..floor((N-1)/2))]):
A:= Vector(N):
for p in Primes do
  t:= 1:
  A[p]:= 1:
  for n from p^2 to N by p do
    if A[n] = 0 then
       t:= t+1:
       A[n]:= t
    fi
  od
od:
0,1,seq(A[i],i=2..N); # Robert Israel, Jan 04 2015

Module[{nn=90,spfs},spfs=Table[FactorInteger[n][[1,1]],{n,nn}];Table[ Count[ Take[spfs,i],spfs[[i]]],{i,nn}]] (* Harvey P. Dale, Sep 01 2014 *)

\\ Not practical for computing, but demonstrates the sum moebius formula:
A020639(n) = { if(1==n,n,vecmin(factor(n)[, 1])); };
A055396(n) = { if(1==n,0,primepi(A020639(n))); };
A002110(n) = prod(i=1, n, prime(i));
A078898(n) = { my(k,p); if(1==n, n, k = A002110(A055396(n)-1); p = A020639(n); sumdiv(k, d, moebius(d)*(n\(p*d)))); };
\\ Antti Karttunen, Dec 05 2014

;; With memoizing definec-macro.
(definec (A078898 n) (if (< n 2) n (+ 1 (A078898 (A249744 n)))))
;; Much better for computing. Needs also code from A249738 and A249744. - Antti Karttunen, Dec 06 2014

Ordinal transform of A020639 (Lpf). - Franklin T. Adams-Watters, Aug 28 2006
From Antti Karttunen, Dec 05-08 2014: (Start)
a(0) = 0, a(1) = 1, a(n) = 1 + a(A249744(n)).
a(0) = 0, a(1) = 1, a(n) = sum_{d | A002110(A055396(n)-1)} moebius(d) * floor(n / (A020639(n)*d)).
a(0) = 0, a(1) = 1, a(n) = sum_{d | A002110(A055396(n)-1)} moebius(d) * floor(A032742(n) / d).
[Instead of Moebius mu (A008683) one could use Liouville's lambda (A008836) in the above formulas, because all primorials (A002110) are squarefree. A020639(n) gives the smallest prime dividing n, and A055396 gives its index].
a(0) = 0, a(1) = 1, a(2n) = n, a(2n+1) = a(A250470(2n+1)). [After a similar recursive formula for A246277. However, this cannot be used for computing the sequence, unless a definition for A250470(n) is found which doesn't require computing the value of A078898(n).]
For n > 1: a(n) = A249810(n) - A249820(n).
(End)
Other identities:
a(2*n) = n.
For n > 1: a(n)=1 if and only if n is prime.
For n > 1: a(n) = A249808(n, A055396(n)) = A249809(n, A055396(n)).
For n > 1: a(n) = A246277(A249818(n)).
From Antti Karttunen, Jan 04 2015: (Start)
a(n) = 2 if and only if n is a square of a prime.
For all n >= 1: a(A251728(n)) = A243055(A251728(n)) + 2. That is, if n is a semiprime of the form prime(i)*prime(j), prime(i) <= prime(j) < prime(i)^2, then a(n) = (j-i)+2.
(End)
a(A000040(n)^2) = 2; a(A000040(n)*A000040(n+1)) = 3. - Reinhard Zumkeller, Apr 06 2015
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Sum_{k>=1} (A038110(k)/A038111(k))^2 = 0.2847976823663... . - Amiram Eldar, Oct 26 2024

a(0) = 0 prepended for recurrence's sake by Antti Karttunen, Dec 06 2014

A083221 Sieve of Eratosthenes arranged as an array and read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Original entry on oeis.org

2, 4, 3, 6, 9, 5, 8, 15, 25, 7, 10, 21, 35, 49, 11, 12, 27, 55, 77, 121, 13, 14, 33, 65, 91, 143, 169, 17, 16, 39, 85, 119, 187, 221, 289, 19, 18, 45, 95, 133, 209, 247, 323, 361, 23, 20, 51, 115, 161, 253, 299, 391, 437, 529, 29, 22, 57, 125, 203, 319, 377, 493, 551, 667

Offset: 2

Yasutoshi Kohmoto, Jun 05 2003

This is permutation of natural numbers larger than 1.
From Antti Karttunen, Dec 19 2014: (Start)
If we assume here that a(1) = 1 (but which is not explicitly included because outside of the array), then A252460 gives an inverse permutation. See also A249741.
For navigating in this array:
A055396(n) gives the row number of row where n occurs, and A078898(n) gives its column number, both starting their indexing from 1.
A250469(n) gives the number immediately below n, and when n is an odd number >= 3, A250470(n) gives the number immediately above n. If n is a composite, A249744(n) gives the number immediately left of n.
First cube of each row, which is {the initial prime of the row}^3 and also the first number neither a prime or semiprime, occurs on row n at position A250474(n).
(End)
The n-th row contains the numbers whose least prime factor is the n-th prime: A020639(T(n,k)) = A000040(n). - Franklin T. Adams-Watters, Aug 07 2015

			The top left corner of the array:
   2,   4,   6,    8,   10,   12,   14,   16,   18,   20,   22,   24,   26
   3,   9,  15,   21,   27,   33,   39,   45,   51,   57,   63,   69,   75
   5,  25,  35,   55,   65,   85,   95,  115,  125,  145,  155,  175,  185
   7,  49,  77,   91,  119,  133,  161,  203,  217,  259,  287,  301,  329
  11, 121, 143,  187,  209,  253,  319,  341,  407,  451,  473,  517,  583
  13, 169, 221,  247,  299,  377,  403,  481,  533,  559,  611,  689,  767
  17, 289, 323,  391,  493,  527,  629,  697,  731,  799,  901, 1003, 1037
  19, 361, 437,  551,  589,  703,  779,  817,  893, 1007, 1121, 1159, 1273
  23, 529, 667,  713,  851,  943,  989, 1081, 1219, 1357, 1403, 1541, 1633
  29, 841, 899, 1073, 1189, 1247, 1363, 1537, 1711, 1769, 1943, 2059, 2117
  ...

Transpose of A083140.
One more than A249741.
Inverse permutation: A252460.
Column 1: A000040, Column 2: A001248.
Row 1: A005843, Row 2: A016945, Row 3: A084967, Row 4: A084968, Row 5: A084969, Row 6: A084970.
Main diagonal: A083141.
First semiprime in each column occurs at A251717; A251718 & A251719 with additional criteria. A251724 gives the corresponding semiprimes for the latter. See also A251728.
Permutations based on mapping numbers between this array and A246278: A249817, A249818, A250244, A250245, A250247, A250249. See also: A249811, A249814, A249815.
Also used in the definition of the following arrays of permutations: A249821, A251721, A251722.
Cf. A002260, A004736, A004280, A020639, A038179, A055396, A078898, A138511, A249820, A249730, A249735, A249744, A250469, A250470, A250472, A250474.

lim = 11; a = Table[Take[Prime[n] Select[Range[lim^2], GCD[# Prime@ n, Product[Prime@ i, {i, 1, n - 1}]] == 1 &], lim], {n, lim}]; Flatten[Table[a[[i, n - i + 1]], {n, lim}, {i, n}]] (* Michael De Vlieger, Jan 04 2016, after Yasutoshi Kohmoto at A083140 *)

More terms from Hugo Pfoertner, Jun 13 2003

A250469 a(1) = 1; and for n > 1, a(n) = A078898(n)-th number k for which A055396(k) = A055396(n)+1, where A055396(n) is the index of smallest prime dividing n.

Original entry on oeis.org

1, 3, 5, 9, 7, 15, 11, 21, 25, 27, 13, 33, 17, 39, 35, 45, 19, 51, 23, 57, 55, 63, 29, 69, 49, 75, 65, 81, 31, 87, 37, 93, 85, 99, 77, 105, 41, 111, 95, 117, 43, 123, 47, 129, 115, 135, 53, 141, 121, 147, 125, 153, 59, 159, 91, 165, 145, 171, 61, 177, 67, 183, 155, 189, 119, 195, 71, 201, 175, 207, 73, 213, 79, 219, 185, 225, 143, 231, 83, 237, 205, 243, 89, 249, 133, 255

Offset: 1

Antti Karttunen, Dec 06 2014

nonn

Permutation of odd numbers.
For n >= 2, a(n) = A078898(n)-th number k for which A055396(k) = A055396(n)+1. In other words, a(n) tells which number is located immediately below n in the sieve of Eratosthenes (see A083140, A083221) in the same column of the sieve that contains n.
A250471(n) = (a(n)+1)/2 is a permutation of natural numbers.
Coincides with A003961 in all terms which are primes. - M. F. Hasler, Sep 17 2016. Note: primes are a proper subset of A280693 which gives all n such that a(n) = A003961(n). - Antti Karttunen, Mar 08 2017

Antti Karttunen, Table of n, a(n) for n = 1..5002

Cf. A000040, A003961, A016945, A046523, A055396, A078898, A083140, A083221, A084967, A249744, A249810, A249820, A249817, A249818, A250471, A266645, A280692, A280693, A283465.

Cf. A250470, A268674 (left inverses, the latter is simpler).

a[1] = 1; a[n_] := If[PrimeQ[n], NextPrime[n], m1 = p1 = FactorInteger[n][[ 1, 1]]; For[k1 = 1, m1 <= n, m1 += p1; If[m1 == n, Break[]]; If[ FactorInteger[m1][[1, 1]] == p1, k1++]]; m2 = p2 = NextPrime[p1]; For[k2 = 1, True, m2 += p2, If[FactorInteger[m2][[1, 1]] == p2, k2++]; If[k1+2 == k2, Return[m2]]]]; Array[a, 100] (* Jean-François Alcover, Mar 08 2016 *)
g[n_] := If[n == 1, 0, PrimePi@ FactorInteger[n][[1, 1]]]; Function[s, MapIndexed[Lookup[s, g[First@ #2] + 1][[#1]] - Boole[First@ #2 == 1] &, #] &@ Map[Position[Lookup[s, g@#], #][[1, 1]] &, Range@ 120]]@ PositionIndex@ Array[g, 10^4] (* Michael De Vlieger, Mar 08 2017, Version 10 *)

a(1) = 1, a(n) = A083221(A055396(n)+1, A078898(n)).
a(n) = A249817(A003961(A249818(n))).
Other identities. For all n >= 1:
A250470(a(n)) = A268674(a(n)) = n. [A250470 and A268674 provide left inverses for this function.]
a(2n) = A016945(n-1). [Maps even numbers to the numbers of form 6n+3, in monotone order.]
a(A016945(n-1)) = A084967(n). [Which themselves are mapped to the terms of A084967, etc. Cf. the Example section of A083140.]
a(A000040(n)) = A000040(n+1). [Each prime is mapped to the next prime.]
For all n >= 2, A055396(a(n)) = A055396(n)+1. [A more general rule.]
A046523(a(n)) = A283465(n). - Antti Karttunen, Mar 08 2017

A250470 a(n) = A249817(A064989(A249818(n))).

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 5, 1, 4, 3, 7, 2, 11, 5, 6, 1, 13, 4, 17, 3, 8, 7, 19, 2, 9, 11, 10, 5, 23, 6, 29, 1, 12, 13, 15, 4, 31, 17, 14, 3, 37, 10, 41, 7, 16, 19, 43, 2, 25, 9, 18, 11, 47, 8, 21, 5, 20, 23, 53, 6, 59, 29, 22, 1, 27, 14, 61, 13, 24, 15, 67, 4, 71, 31, 26, 17, 35, 22, 73, 3, 28, 37, 79, 10, 33, 41, 30, 7, 83, 12, 55, 19, 32, 43, 39, 2, 89, 25, 34, 9, 97, 26, 101

Offset: 1

Antti Karttunen, Dec 06 2014

nonn

Odd bisection, A250472, is a permutation of natural numbers. A250479 gives the even bisection.

For odd numbers n >= 3, a(n) = A078898(n)-th number k for which A055396(k) = A055396(n)-1. In other words, a(n) tells which number is located immediately above n in the sieve of Eratosthenes (see A083140, A083221) in the same column of the sieve that contains n.

Antti Karttunen, Table of n, a(n) for n = 1..9048

Cf. A055396, A064989, A078898, A083140, A083221, A249744, A249810, A249820, A249817, A249818, A250469.
Odd bisection: A250472.
Even bisection: A250479.
Differs from A064989 for the first time at n=21, where a(21) = 8, while
A064989(21) = 10.

(define (A250470 n) (A249817 (A064989 (A249818 n))))

a(n) = A249817(A064989(A249818(n))).
Other identities. For all n >= 1:
a(A250469(n)) = n. [This is an inverse function for injection A250469.]
For all odd numbers n >= 3: A055396(a(n)) = A055396(n)-1.

A249738 a(n) = 0 if n is 1 or a prime, otherwise, when n = A020639(n) * A032742(n), a(n) = the largest k < A032742(n) such that either k = 1 or A020639(k) >= A020639(n), where A020639(n) and A032742(n) are the smallest prime and the largest proper divisor dividing n.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 0, 3, 1, 4, 0, 5, 0, 6, 3, 7, 0, 8, 0, 9, 5, 10, 0, 11, 1, 12, 7, 13, 0, 14, 0, 15, 9, 16, 5, 17, 0, 18, 11, 19, 0, 20, 0, 21, 13, 22, 0, 23, 1, 24, 15, 25, 0, 26, 7, 27, 17, 28, 0, 29, 0, 30, 19, 31, 11, 32, 0, 33, 21, 34, 0, 35, 0, 36, 23, 37, 7, 38, 0, 39, 25, 40, 0, 41, 13, 42, 27, 43, 0, 44, 11, 45, 29, 46, 17, 47, 0, 48, 31, 49, 0, 50

Offset: 1

Antti Karttunen, Dec 06 2014

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A020639, A032742, A078898, A249744.

(define (A249738 n) (cond ((or (= 1 n) (prime? n)) 0) (else (let ((lpf (A020639 n))) (let loop ((k (- (A032742 n) 1))) (cond ((= 1 k) k) ((>= (A020639 k) lpf) k) (else (loop (- k 1)))))))))

Other identities:
a(n) = A249744(n) / A020639(n).
a(k) = 1 if and only if k is one of A001248 (squares of primes).

cp's OEIS Frontend

A078898 Number of times the smallest prime factor of n is the smallest prime factor for numbers <= n; a(0)=0, a(1)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Scheme

Formula

Extensions

A083221 Sieve of Eratosthenes arranged as an array and read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A250469 a(1) = 1; and for n > 1, a(n) = A078898(n)-th number k for which A055396(k) = A055396(n)+1, where A055396(n) is the index of smallest prime dividing n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A250470 a(n) = A249817(A064989(A249818(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A249738 a(n) = 0 if n is 1 or a prime, otherwise, when n = A020639(n) * A032742(n), a(n) = the largest k < A032742(n) such that either k = 1 or A020639(k) >= A020639(n), where A020639(n) and A032742(n) are the smallest prime and the largest proper divisor dividing n.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula