A003586 -id:A003586 - cp's OEIS frontend

A290365 Numbers that cannot be written as a difference of 3-smooth numbers (A003586).

41, 43, 59, 67, 82, 83, 85, 86, 89, 91, 97, 103, 109, 113, 118, 121, 123, 129, 131, 133, 134, 137, 145, 149, 151, 155, 157, 163, 164, 166, 167, 169, 170, 172, 173, 177, 178, 181, 182, 185, 187, 193, 194, 197, 199, 201, 203, 205, 206, 209, 218, 221, 223, 226

Offset: 1

Michel Marcus, Aug 03 2017

nonn

Called ndh-numbers in the da Silva et al. link.
From Jon E. Schoenfield, Aug 19 2017: (Start)
If (following da Silva et al.) we refer to these numbers as "ndh-numbers" (meaning that they cannot be expressed as the difference of two "harmonic numbers" [which, in this context, are 3-smooth numbers]), we could refer to the sequence of positive integers that are not in this sequence as "dh-numbers", and say that the set of positive integers <= 100 includes the 11 ndh-numbers listed at the link (i.e., a(1) = 41 through a(11) = 97) and 100 - 11 = 89 dh-numbers. Each of the 89 dh-numbers <= 100 can be written as the difference of two 3-smooth numbers using no 3-smooth number larger than 162 (which is required to obtain the difference 98 = 162 - 64). The table below shows results from checking every difference between two 3-smooth numbers < 10^50 (which seems very nearly certain to capture all differences in [1,10^10]):
.
    Number    Number
    of ndh-   of dh-
    numbers   numbers
      in        in     Largest 3-smooth number required
k  [1,10^k]  [1,10^k]   to obtain a dh-number in [1,10^k]
=  ========  ========  ==================================
1         0        10          12 =          3 +        9
2        11        89         162 =         64 +       98
3       522       478       13122 =      12288 +      834
4      8433      1567      531441 =     524288 +     7153
5     96065      3935     6377292 =    6291456 +    85836
6    991699      8301    68024448 =   67108864 +   915584
7   9984463     15537   688747536 =  679477248 +  9270288
8  99973546     26454  7346640384 = 7247757312 + 98883072
.
A101082 gives the numbers that cannot be written as a difference of 2-smooth numbers (i.e., the powers of 2: A000079).
Numbers that cannot be written as a difference of 5-smooth numbers (A051037) appear to be 281, 289, 353, 413, 421, 439, 443, 457, 469, 493, 541, 562, 563, 578, 581, 583, 641, 653, 661, 677, 683, 691, 701, 706, 707, 731, 733, 737, 751, 761, 769, 779, 787, 793, 803, 811, 817, 823, 826, 827, 829, 841, 842, 843, 853, 857, 867, 877, 878, 881, 883, 886, ...
Numbers that cannot be written as a difference of 7-smooth numbers (A002473) appear to be 1849, 2309, 2411, 2483, 2507, 2531, 2629, 2711, 2753, 2843, 2851, 2921, 2941, 3139, 3161, 3167, 3181, 3217, 3229, 3251, 3287, 3289, 3293, 3323, 3379, 3481, 3487, 3541, 3601, 3623, 3653, 3697, 3698, 3709, 3737, 3739, 3803, 3827, 3859, 3877, 3901, 3923, 3947, ...
Numbers that cannot be written as a difference of 11-smooth numbers (A051038) appear to be 9007, 10091, 10531, 10831, 11801, 12197, 12431, 12833, 12941, 13393, 13501, 13619, 13679, 13751, 13907, 13939, 14219, 14423, 14737, 14851, 14893, 15217, 15641, 15767, 15773, 15803, 15959, 16019, 16201, 16241, 16393, 16397, 16417, 16441, 16517, 16559, 16579, ...
(End)

Natalia da Silva, Serban Raianu, Hector Salgado, Differences of Harmonic Numbers and the abc-Conjecture, arXiv:1708.00620 [math.NT], 2017.

Cf. A000079, A002473, A003586, A051037, A051038, A101082.

terms = 54;
A3586 = Select[Range[3000], FactorInteger[#][[-1, 1]] <= 3&];
dd = Union[#[[2]] - #[[1]]& /@ Subsets[A3586, {2}]];
Complement[Range[u[[-1]]], dd][[1 ;; terms]] (* Jean-François Alcover, Sep 28 2018 *)

a(12)-a(54) from Jon E. Schoenfield, Aug 18 2017

A057561 Size of the largest set encompassing no {x, 2x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, ...} (A003586).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

nonn

This is the weakly triple-free analog of A157271.
A094708(n) = n - a(n).
Position of first n gives A004059(n).
Graham paper erroneously has a(30)=20. - Sean A. Irvine, Nov 18 2015

			A set for a(30) is {1, 2, 6, 8, 9, 12, 16, 27, 36, 48, 54, 64, 72, 96, 128, 162, 216, 243, 256, 288, 324}. - _Sean A. Irvine_, Oct 26 2015

R. L. Graham et al., On extremal density theorems for linear forms, pp. 103-109 of H. Zassenhaus, editor, Number Theory and Algebra. Academic Press, NY, 1977.

F. Chung, P. Erdős, R. Graham, On sparse sets hitting linear forms, Proc. Number Theory for the Millennium, 1, pp. 257-272, 2000.
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
R. L. Graham et al., On extremal density theorems for linear forms, pp. 103-109 of H. Zassenhaus, editor, Number Theory and Algebra. Academic Press, NY, 1977.

Cf. A004059, A094708, A003586, A157271.

Edited by Steven Finch, Feb 25 2009
Revised by N. J. A. Sloane, Jun 13 2012
a(30) corrected and more terms from Sean A. Irvine, Oct 26 2015

A086420 Euler's totient of 3-smooth numbers: a(n) = A000010(A003586(n)).

Original entry on oeis.org

1, 1, 2, 2, 2, 4, 6, 4, 8, 6, 8, 18, 16, 12, 16, 18, 32, 24, 54, 32, 36, 64, 48, 54, 64, 72, 162, 128, 96, 108, 128, 144, 162, 256, 192, 216, 486, 256, 288, 324, 512, 384, 432, 486, 512, 576, 648, 1024, 1458, 768, 864, 972, 1024, 1152, 1296, 2048, 1458, 1536

Offset: 1

Reinhard Zumkeller, Jul 18 2003

nonn

a(n) is 3-smooth.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Totient Function.
Eric Weisstein's World of Mathematics, Smooth Number.

Cf. A000010, A003586.

s = {}; m = 12; Do[n = 3^k; While[n <= 3^m, AppendTo[s, n]; n*=2], {k, 0, m}]; EulerPhi /@ Union[s] (* Amiram Eldar, Jan 29 2020 *)

n>1: a(n) = A003586(n) * (if A003586(n) mod 3 > 0 then 1/2 else (1 + A003586(n) mod 2)/3), a(1) = 1.

Sum_{n>=1} 1/a(n) = 21/4. - Amiram Eldar, Dec 21 2020

A094708 Size of the smallest set hitting all {x, 2x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27,...} (A003586).

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 13, 13, 13, 13, 13, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 21

Offset: 1

Barry Cipra, Jun 15 2004

nonn

A057561(n) = n - a(n). [Steven Finch, Feb 25 2009]

F. Chung, P. Erdős and R. L. Graham, On Sparse Sets Hitting Linear Forms, in Number Theory for the Millennium I (M. A. Bennett et al., eds.), 2002, pp. 257-272.
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]

Cf. A003586, A057561.

More terms from Sean A. Irvine, Nov 19 2015

A186712 Smallest number m such that A186711(m) = A003586(n).

Original entry on oeis.org

1, 4, 7, 8, 10, 17, 18, 14, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 36, 38, 39, 41, 42, 43, 45, 46, 93, 94, 50, 51, 53, 54, 104, 105, 58, 59, 111, 112, 63, 116, 117, 67, 68, 123, 124, 72, 128, 129, 131, 132, 78, 136, 137, 82, 141, 142, 144, 145, 88, 149, 150, 152, 153, 155, 156, 158, 159, 99, 163, 164, 166, 167, 169, 170, 172, 173, 175, 176, 178, 179

Offset: 1

Reinhard Zumkeller, Feb 26 2011

nonn

A186711(a(n)) = A003586(n) and A186711(m) != A003586(n) for m < a(n).

			n = 10: A003586(10) = 18 and A186711(23) = 18 with no preceding occurrences of 18 in A186711.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A003586, A186711.

import Data.List  (findIndex); import Data.Maybe (fromJust)
a186712 n = (+ 1) $ fromJust $ findIndex (== a003586 n) a186711_list

A186712 := proc(n) for m from 1 do if A186711(m) = A003586(n) then return m; end if; end do: end proc: # R. J. Mathar, Mar 04 2011

A301574 a(n) = distance from n to nearest 3-smooth number (A003586).

Original entry on oeis.org

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

Offset: 1

Altug Alkan and Rémy Sigrist, Mar 23 2018

This sequence is unbounded.

A053646 is the corresponding sequence for 2-smooth numbers (A000079).

			a(20) = a(22) = 2 because 18 is the nearest 3-smooth number to 20 and 24 is the nearest 3-smooth number to 22.

Altug Alkan, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program for A301574
Index entries for sequences related to distance to nearest element of some set

Cf. A000079, A003586, A053646.

PARI
```
\\ See Links section.
```

from sympy import integer_log
def A301574(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return x-sum((x//3**i).bit_length() for i in range(integer_log(x,3)[0]+1))
    k = n-f(n)
    return min(n-bisection(lambda x:f(x)+k,k,k),bisection(lambda x:f(x)+k+1,n,n)-n) # Chai Wah Wu, Oct 22 2024

a(n) = 0 iff n belongs to A003586.
2 * a(n) >= a(2 * n).
3 * a(n) >= a(3 * n).

A309015 2-highly composite numbers: 3-smooth numbers (A003586) k with d(k) > d(j) for all 3-smooth numbers j < k, where d(k) is the number of divisors of k (A000005).

Original entry on oeis.org

1, 2, 4, 6, 12, 24, 36, 48, 72, 144, 216, 288, 432, 576, 864, 1296, 1728, 2592, 3456, 5184, 6912, 10368, 15552, 20736, 31104, 41472, 62208, 82944, 93312, 124416, 186624, 248832, 373248, 497664, 746496, 995328, 1119744, 1492992, 2239488, 2985984, 4478976, 5971968

Offset: 1

Amiram Eldar, Jul 06 2019

nonn

Also numbers with record numbers of divisors among the numbers with at most 2 distinct prime factors (A070915).
Bessi and Nicolas proved that there exists a constant c such that the number of 2-highly composite numbers smaller than x is larger than c*(log(x))^(4/3).
In general, k-highly composite numbers (defined by Nicolas, 2005) are numbers with a record number of divisors where only p(k)-smooth numbers are being considered. Equivalently only numbers with at most k distinct prime factors can be considered.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Pascal Alessandri and Valérie Berthé, Three distance theorems and combinatorics on words, Enseignement Mathématique, Vol. 44 (1998), pp. 103-132.
Gérard Bessi, Etude des nombres 2-hautement composés, Séminaire de Théorie des nombres de Bordeaux, Vol. 4 (1975), pp. 1-22.
Gérard Bessi and J. L. Nicolas, Nombres 2-hautement composés, J. Math. pures et appl., Vol. 56 (1977), pp. 307-326.
Amiram Eldar, Table of n, a(n), A000005(a(n)) for n = 1..10000
Jean-Louis Nicolas, Some open questions, The Ramanujan Journal, Vol. 9 (2005), pp. 251-264.

Cf. A000005, A002182, A003586, A070915.

dmax = 0; s = {}; Do[If[EulerPhi[6n] == 2n, d = DivisorSigma[0, n]; If[d > dmax, dmax = d; AppendTo[s, n]]], {n, 1, 10^4}]; s (* after Artur Jasinski at A003586 *)
Block[{n = 10^7, s, t}, s = Union@ Flatten@ Table[2^a * 3^b, {a, 0, Log2@ n}, {b, 0, Log[3, n/(2^a)]}]; t = DivisorSigma[0, s]; Map[s[[FirstPosition[t, #][[1]] ]] &, Union@ FoldList[Max, t]]] (* Michael De Vlieger, Jul 09 2019 *)

A157271 Size of the largest set encompassing no {x, 2x} nor {x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27,...} (A003586).

Original entry on oeis.org

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

Offset: 1

Steven Finch, Feb 26 2009

nonn

This is the strongly triple-free analog of A057561 and the description is modeled after A094708.

a(n) is the size of the maximal independent set in a grid graph with vertex set D(n) and edges connecting every x to 2x and every x to 3x.

			For n=7, the grid graph has rows {1,3,9}, {2,6}, {4}, {8} and the maximal set of nonadjacent vertices is {1,4,6,9}, hence a(7)=4.

Giovanni Resta, Table of n, a(n) for n = 1..1000
J. Cassaigne and P. Zimmermann, Numerical Evaluation of the Strongly Triple-Free Constant.
Julien Cassaigne and Paul Zimmermann, Numerical Evaluation of the Strongly Triple-Free Constant (pdf file, 1996).
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]

Cf. A057561, A094708.

f[k_,n_]:=1+Floor[FullSimplify[Log[n/3^k]/Log[2]]]; g[n_]:=Floor[FullSimplify[Log[n]/Log[3]]]; peven[n_]:=Sum[Quotient[f[k,n]+Mod[k+1,2],2],{k,0,g[n]}]; podd[n_]:=Sum[Quotient[f[k,n]+Mod[k,2],2],{k,0,g[n]}]; p[n_]:=Max[peven[n],podd[n]]; v[1]=1;j=1;k=1;n=70; For[k=2, k<=n, k++, If[2*v[k-j]<3^j,v[k]=2*v[k-j],{v[k]=3^j,j++}]]; Table[p[v[n]],{n,1,70}] (* Steven Finch, Feb 27 2009; corrected by Giovanni Resta, Jul 29 2015 *)

A247714 Position of A036561(n) in sequence A003586.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 6, 8, 10, 12, 9, 11, 14, 16, 19, 13, 15, 18, 21, 24, 27, 17, 20, 23, 26, 30, 33, 37, 22, 25, 29, 32, 36, 40, 44, 49, 28, 31, 35, 39, 43, 47, 52, 57, 62, 34, 38, 42, 46, 51, 55, 60, 66, 71, 77, 41, 45, 50, 54, 59, 64, 69, 75, 81, 87, 93, 48

Offset: 0

Michel Marcus, Sep 22 2014

nonn

Motivated by L. Edson Jeffery comment in A036561 that says it is a permutation of A003586.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A003586, A036561.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a247714 = (+ 1) . fromJust .
                  (`elemIndex` a003586_list) . (a036561_list !!)
-- Reinhard Zumkeller, Sep 23 2014

N0:= 10: # to get the first (N0+1)*(N0+2)/2 terms
V:= 3^N0:
S:= {seq(seq(2^i*3^j, i=0..ilog2(V/3^j)),j=0..N0)}:
# in Maple 11 or earlier, uncomment the next line and comment out the previous one
# S:= sort([seq(seq(2^i*3^j, i=0..ilog2(V/3^j)),j=0..N0)]):
for k from 1 to nops(S) do
  r:= S[k];
  jr:= padic[ordp](r,3);
  ir:= jr + padic[ordp](r,2);
  A[1+jr+ir*(ir+1)/2] := k;
od:
seq(A[k],k=1..(N0+1)*(N0+2)/2); # Robert Israel, Sep 22 2014

lista(nn) = {w = readvec("b036561.txt"); v = readvec("b003586.txt"); for (i=1, nn, print1(setsearch(v, w[i], 0), ", "););}

A261255 Where MU-numbers (cf. A007335) occur in A003586 (3-smooth numbers).

Original entry on oeis.org

2, 3, 5, 8, 10, 11, 15, 16, 20, 24, 25, 26, 31, 33, 38, 39, 44, 45, 47, 53, 54, 57, 61, 64, 70, 71, 72, 75, 80, 83, 87, 90, 92, 96, 101, 104, 105, 109, 113, 115, 119, 123, 125, 129, 134, 138, 140, 144, 145, 149, 151, 156, 161, 165, 166, 168, 173, 178, 180

Offset: 1

Reinhard Zumkeller, Aug 13 2015

nonn

			.   n |   A007335(n)     | a(n) | A003586(a(n))
.  ---+------+-----------+------+--------------
.   1 |    2 |         2 |    2 |            2
.   2 |    3 |         3 |    3 |            3
.   3 |    6 |     2 * 3 |    5 |            6
.   4 |   12 |   2^2 * 3 |    8 |           12
.   5 |   18 |   2 * 3^2 |   10 |           18
.   6 |   24 |   2^3 * 3 |   11 |           24
.   7 |   48 |   2^4 * 3 |   15 |           48
.   8 |   54 |   2 * 3^3 |   16 |           54
.   9 |   96 |   2^5 * 3 |   20 |           96
.  10 |  162 |   2 * 3^4 |   24 |          162
.  11 |  192 |   2^6 * 3 |   25 |          192
.  12 |  216 | 2^3 * 3^3 |   26 |          216 .

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A007335, A003586.

import Data.List (findIndex); import Data.Maybe (fromJust)
a261255 n = fromJust (findIndex (== a007335 n) a003586_list) + 1

A007335(n) = A003586(a(n)).

cp's OEIS Frontend

A290365 Numbers that cannot be written as a difference of 3-smooth numbers (A003586).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A057561 Size of the largest set encompassing no {x, 2x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, ...} (A003586).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A086420 Euler's totient of 3-smooth numbers: a(n) = A000010(A003586(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A094708 Size of the smallest set hitting all {x, 2x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27,...} (A003586).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A186712 Smallest number m such that A186711(m) = A003586(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

A301574 a(n) = distance from n to nearest 3-smooth number (A003586).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A309015 2-highly composite numbers: 3-smooth numbers (A003586) k with d(k) > d(j) for all 3-smooth numbers j < k, where d(k) is the number of divisors of k (A000005).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A157271 Size of the largest set encompassing no {x, 2x} nor {x, 3x} contained in D(n) = the first n 3-smooth numbers {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27,...} (A003586).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs