Square-free integers: Difference between revisions

=={{header|jq}}==

Requires jq 1.5 or higher

For brevity and in order to highlight some points of interest regarding jq,

this entry focuses on solving the task in a manner that reflects

the specification as closely as possible (no prime sieves or calls

to sqrt), with efficiency concerns playing second fiddle.

Once a suitable generator for squares and a test for divisibility have been written, the

test for whether a number is square-free can be written in one line:

def square_free: . as $n | all( squares; divides($n) | not);

In words: to verify whether an integer, $n, is square_free, check that no admissible square divides $n.

'''squares'''

We could define the required `squares` generator using `while`:

def squares: . as $n | 2 | while(.*. <= $n; .+1) | .*.;

(Here `.*.` calculates the square of the input number.)

However, this entails performing an unnecessary multiplication, so the question becomes whether there

is a more economical solution that closely reflects the specification of the required generator. Since jq supports tail-recursion optimization for 0-arity filters, the answer is:

def squares:

. as $n

| def s:

(.*.) as $s

| select($s <= $n)

| $s, ((1+.)|s);

2|s;

The point of interest here is the def-within-a-def.

'''divides'''

def divides($x): ($x % .) == 0;

'''is_square_free'''

`is_square_free` as defined here intentionally returns true for all numeric inputs less than 4.

def is_square_free: . as $n | all( squares; divides($n) | not) ;

----

'''The tasks'''

The primary task is to examine square-free numbers in an inclusive range,

so we define `square_free` to emit a stream of such numbers:

def square_free(from; including):

range(from;including+1) | select( is_square_free ) ;

# Compute SIGMA(s) where s is a stream

def sigma(s): reduce s as $s (null; .+$s);

# Group items in a stream into arrays of length at most $n.

# For generality, this function uses `nan` as the eos marker.

def nwise(stream; $n):

foreach (stream, nan) as $x ([];

if length == $n then [$x] else . + [$x] end;

if (.[-1] | isnan) and length>1 then .[:-1]

elif length == $n then .

else empty

end);

def prettify_squares(from; including; width):

"Square-free integers from \(from) to \(including) (inclusive):",

(nwise( square_free(from;including); width) | map(tostring) | join(" ")),

"";

def prettify_count($from; $including):

"Count from \($from) to \($including) inclusive: \(sigma( square_free($from ; $including) | 1 ))";

'''The specific tasks'''

prettify_squares(1;145; 20),

prettify_squares(1E12; 1E12 + 145; 5),

((1E2, 1E3, 1E4, 1E5, 1E6) | prettify_count(1; .))

'''Output'''

<pre>Square-free integers from 1 to 145 (inclusive):

1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31

33 34 35 37 38 39 41 42 43 46 47 51 53 55 57 58 59 61 62 65

66 67 69 70 71 73 74 77 78 79 82 83 85 86 87 89 91 93 94 95

97 101 102 103 105 106 107 109 110 111 113 114 115 118 119 122 123 127 129 130

131 133 134 137 138 139 141 142 143 145

Square-free integers from 1000000000000 to 1000000000145 (inclusive):

1000000000001 1000000000002 1000000000003 1000000000005 1000000000006

1000000000007 1000000000009 1000000000011 1000000000013 1000000000014

1000000000015 1000000000018 1000000000019 1000000000021 1000000000022

1000000000023 1000000000027 1000000000029 1000000000030 1000000000031

1000000000033 1000000000037 1000000000038 1000000000039 1000000000041

1000000000042 1000000000043 1000000000045 1000000000046 1000000000047

1000000000049 1000000000051 1000000000054 1000000000055 1000000000057

1000000000058 1000000000059 1000000000061 1000000000063 1000000000065

1000000000066 1000000000067 1000000000069 1000000000070 1000000000073

1000000000074 1000000000077 1000000000078 1000000000079 1000000000081

1000000000082 1000000000085 1000000000086 1000000000087 1000000000090

1000000000091 1000000000093 1000000000094 1000000000095 1000000000097

1000000000099 1000000000101 1000000000102 1000000000103 1000000000105

1000000000106 1000000000109 1000000000111 1000000000113 1000000000114

1000000000115 1000000000117 1000000000118 1000000000119 1000000000121

1000000000122 1000000000123 1000000000126 1000000000127 1000000000129

1000000000130 1000000000133 1000000000135 1000000000137 1000000000138

1000000000139 1000000000141 1000000000142 1000000000145

Count from 1 to 100 inclusive: 61

Count from 1 to 1000 inclusive: 608

Count from 1 to 10000 inclusive: 6083

Count from 1 to 100000 inclusive: 60794

Count from 1 to 1000000 inclusive: 607926</pre>