11
\$\begingroup\$

If 1 is not counted as a factor, then

  • 40 has two neighboring factors (4 and 5)
  • 1092 has two neighboring factors (13 and 14)
  • 350 does not have two neighboring factors (out of its factors 2, 5, 7, 10, 14, 25, 35, 50, 70, and 175, no two are consecutive)

The proportion of positive integers that have this property is the proportion divisible by any of 6 (2 × 3), 12 (3 × 4), 20 (4 × 5), 30, 56, …. If we only calculate the proportion divisible by the first n of these, we get an approximation that gets more accurate as n increases.

For example, for n=1, we find the proportion of integers divisible by 2 × 3 = 6, which is 1/6. For n=2, all integers divisible by 3 × 4 = 12 are also divisible by 6, so the approximation is still 1/6. For n=3, the proportion of integers divisible by 6 or 20 is 1/5, and so on.

Here are the first few values:

1  1/6                0.16666666666666666
3  1/5                0.20000000000000000
6  22/105             0.20952380952380953
9  491/2310           0.21255411255411255
12 2153/10010         0.21508491508491510
15 36887/170170       0.21676558735382265
21 65563/301070       0.21776663234463747
24 853883/3913910     0.21816623274423785
27 24796879/113503390 0.21846817967287144

For values of n between the provided values, the output should be the same as the output for the value above (e.g. n=5 → 1/5).

Your program should take n and output either a fraction or decimal answer. You may take n at any offset (e.g. 0-indexing or 2-indexing into this sequence, instead of 1-indexing).

For decimal output, your program must be accurate to at least 5 digits for all the test cases given.

Scoring is , with the shortest code winning.

Inspired by What proportion of positive integers have two factors that differ by 1? by marty cohen -- specifically, by Dan's answer.

\$\endgroup\$
  • 1
    \$\begingroup\$ How accurate does a decimal answer have to be? A natural strategy seems to be to count the integers with a valid divisor in some enormous range and divide by the length of the range, which gets better as an approximation as the range gets bigger. \$\endgroup\$ – xnor Dec 16 '18 at 19:07
  • \$\begingroup\$ @xnor I've now addressed that in the post. \$\endgroup\$ – Doorknob Dec 16 '18 at 19:45
6
\$\begingroup\$

Jelly,  14 13  10 bytes

-1 using Erik the Outgolfer's idea to take the mean of a list of zeros and ones.
-3 by using 3-indexing (as allowed in the question) - thanks to Dennis for pointing this out.

ḊPƝḍⱮ!Ẹ€Æm

A monadic Link accepting an integer, n+2, which yields a float.

Try it online! (very inefficient since it tests divisibility over the range \$[2, (n+2)!]\$)

(Started out as +2µḊPƝḍⱮ!§T,$Ẉ, taking n and yielding [numerator, denominator], unreduced)

How?

ḊPƝḍⱮ!Ẹ€Æm - Link: integer, x=n+2
Ḋ          - dequeue (implicit range of) x  - i.e. [2,3,4,...,n+2]
  Ɲ        - apply to neighbours:
 P         -   product                             [2×3,3×4,...,(n+1)×(n+2)]
     !     - factorial of x                        x!
    Ɱ      - map across (implicit range of) x! with:
   ḍ       -   divides?                            [[2×3ḍ1,3×4ḍ1,...,(n+1)×(n+2)ḍ1],[2×3ḍ2,3×4ḍ2,...,(n+1)×(n+2)ḍ2],...,[2×3ḍ(x!),3×4ḍ(x!),...,(n+1)×(n+2)ḍ(x!)]]
       €   - for each:
      Ẹ    -   any?  (1 if divisible by any of the neighbour products else 0)
        Æm - mean
\$\endgroup\$
  • \$\begingroup\$ Hm... I suspect what makes this shorter than mine is the use of ! instead of æl/... Ah, the joys of rules changing while sleeping. \$\endgroup\$ – Erik the Outgolfer Dec 17 '18 at 12:41
  • \$\begingroup\$ @EriktheOutgolfer yeah, very similar methods when I look closer! can you use P to get down to 13? \$\endgroup\$ – Jonathan Allan Dec 17 '18 at 13:08
  • \$\begingroup\$ Instead of Ẹ€? I'm afraid P is the same as ׃1$, so it won't work. (And that would be 14 anyway...) If instead of æl/, maybe (P is LCM*k after all). \$\endgroup\$ – Erik the Outgolfer Dec 17 '18 at 13:09
  • \$\begingroup\$ @EriktheOutgolfer instead of æl/ \$\endgroup\$ – Jonathan Allan Dec 17 '18 at 13:10
  • \$\begingroup\$ Yeah, I think I can do that, and the result would theoretically be as precise as with æl/ I guess. (Night-owl golfing does have issues...) EDIT: Yeah, although I'll have to reduce the argument over TIO to 4... :P \$\endgroup\$ – Erik the Outgolfer Dec 17 '18 at 13:12
3
\$\begingroup\$

05AB1E, 15 bytes

Ì©!Lε®LüP¦Öà}ÅA

Port of @JonathanAllan's Jelly answer, so also extremely slow.

Try it online or verify the first three test cases.

Explanation:

Ì                 # Add 2 to the (implicit) input
                  #  i.e. 3 → 5
 ©                # Store this in the register (without popping)
  !               # Take the factorial of it
                  #  i.e. 5 → 120
   L              # Create a list in the range [1, (input+2)!]
                  #   i.e. 120 → [1,2,3,...,118,119,120]
    ε       }     #  Map over each value in this list
     ®            #  Push the input+2 from the register
      L           #  Create a list in the range [1, input+2]
                  #   i.e. 5 → [1,2,3,4,5]
       ü          #  Take each pair
                  #    i.e. [1,2,3,4,5] → [[1,2],[2,3],[3,4],[4,5]]
        P         #   And take the product of that pair
                  #    i.e. [[1,2],[2,3],[3,4],[4,5]] → [2,6,12,20]
         ¦        #  Then remove the first value from this product-pair list
                  #   i.e. [2,6,12,20] → [6,12,20]
          Ö       #  Check for each product-pair if it divides the current map-value
                  #  (1 if truthy; 0 if falsey)
                  #   i.e. [1,2,3,...,118,119,120] and [6,12,20]
                  #    → [[0,0,0],[0,0,0],[0,0,0],...,[0,0,0],[0,0,0],[1,1,1]]
           à      #  And check if it's truthy for any by taking the maximum
                  #   i.e. [[0,0,0],[0,0,0],[0,0,0],...,[0,0,0],[0,0,0],[1,1,1]]
                  #    → [0,0,0,...,0,0,1]
             ÅA   # After the map, take the mean (and output implicitly)
                  #  i.e. [0,0,0,...,0,0,1] → 0.2
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6),  94 92  90 bytes

Saved 2 bytes thanks to @Shaggy + 2 more bytes from there

Returns a decimal approximation.

n=>(x=2,g=a=>n--?g([...a,x*++x]):[...Array(1e6)].map((_,k)=>n+=a.some(d=>k%d<1))&&n/1e6)``

Try it online!


JavaScript (ES6), 131 bytes

A much longer solution that returns an exact result as a pair \$[numerator, denominator]\$.

f=(n,a=[],p=x=1)=>n?f(n-1,[...a,q=++x*-~x],p*q/(g=(a,b)=>a?g(b%a,a):b)(p,q)):[...Array(p)].map((_,k)=>n+=a.some(d=>-~k%d<1))&&[n,p]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ -2 bytes \$\endgroup\$ – Shaggy Dec 16 '18 at 21:49
  • \$\begingroup\$ This should work, in theory for 82 bytes. \$\endgroup\$ – Shaggy Dec 17 '18 at 10:25
  • \$\begingroup\$ @Shaggy I don't really know what the consensus is for answers like that. While it does work in theory, it doesn't work in practice for any input. (I personally dislike this kind of answers. This is why I usually include a rule such as "your code should at least work up to a given limit" in my own challenges when I suspect that I'll get answers such as "works only for n=1 on TIO" ... or doesn't work at all in the present case.) \$\endgroup\$ – Arnauld Dec 17 '18 at 10:34
  • \$\begingroup\$ Personally, I'm a big fan of the infinite time & memory consensus ;) \$\endgroup\$ – Shaggy Dec 17 '18 at 11:47
  • \$\begingroup\$ Oh I like it too. :) My only reservation is that I think it should be possible to test any answer for at least a couple of distinct inputs. \$\endgroup\$ – Arnauld Dec 17 '18 at 12:14
3
\$\begingroup\$

Jelly, 12 bytes

Ḋב$ḍẸ¥ⱮP$Æm

Try it online!

-2 thanks to Jonathan Allan's suggestion to replace the LCM with the product (i.e. the LCM multiplied by an integer).

Dennis noticed I can 2-index as well.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 26 bytes

FN⊞υ×⁺²ι⁺³ιI∕LΦΠυ¬⌊Eυ﹪ιλΠυ

Try it online! Link is to verbose version of code. Hopelessly inefficient (O(n!²)) so only works up to n=4 on TIO. Explanation:

FN⊞υ×⁺²ι⁺³ι

Input n and calculate the first n products of neighbouring factors.

I∕LΦΠυ¬⌊Eυ﹪ιλΠυ

Take the product of all of those factors and use that to calculate the proportion of numbers having at least one of those factors.

30-byte less slow version is only O(n!) so can do up to n=6 on TIO:

F⊕N⊞υ⁺²ιI∕LΦΠυΣEυ∧μ¬﹪ι×λ§υ⊖μΠυ

Try it online! Link is to verbose version of code.

46-byte faster version is only O(lcm(1..n+2)) so can do up to n=10 on TIO:

FN⊞υ×⁺²ι⁺³ι≔⁰η≔⁰ζW∨¬η⌈Eυ﹪ηκ«≦⊕η≧⁺⌈Eυ¬﹪ηκζ»I∕ζη

Try it online! Link is to verbose version of code.

45-byte faster version is only O(2ⁿ) so can do up to n=13 on TIO:

⊞υ±¹FEN×⁺²ι⁺³ιF⮌υ⊞υ±÷×ικ⌈Φ⊕ι∧λ¬∨﹪ιλ﹪κλIΣ∕¹✂υ¹

Try it online! Link is to verbose version of code.

54-byte fastest version uses more efficient LCM so can do up to n=18 on TIO:

⊞υ±¹FEN×⁺²ι⁺³ιFEυ⟦κι⟧«W⊟κ⊞⊞Oκλ﹪§κ±²λ⊞υ±÷Π…κ²⊟κ»IΣ∕¹✂υ¹

Try it online! Link is to verbose version of code.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 69 68 61 52 bytes

Count[Range[#!],b_/;Or@@(# #-#&@Range[3,#]∣b)]/#!&

Try it online!

3-indexed. At first I was going to use LCM@@ but realized that #! would be shorter... but now it a lot of memory for Range[#!]...

Managed to golf down the condition by 2 bytes, which was nice.


Older numerical solution (56 bytes):

N@Count[Range[5^8],b_/;Or@@Array[(# #-#)∣b&,#,3]]/5^8&

Try it online!

2-indexed. More efficient when #!>5^8 (#>9, assuming # is an integer).

\$\endgroup\$
1
\$\begingroup\$

Python 2, 78 bytes

lambda n:sum(any(-~i%(j*-~j)<1for j in range(2,n+2))for i in range(10**7))/1e7

Try it online!

Returns the approximate decimal to +5 digits; uses the naive brute force approach xnor suggests in comments on the question.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.