13
\$\begingroup\$

Hamming number (also known as regular number) is a number that evenly divides powers of 60. We already have a task to do something with it. This time we are going to do the opposite.

I define non-Hamming number as in: \$n\$ is non-Hamming number if and only if it satisfies following two conditions:

  • \$n\$ is positive integer, and
  • \$n\$ does not divide powers of 60 evenly; i.e. \$60^m\mod n\neq0\$ for all positive integer \$m\$.

Make a program, a function, or a subroutine that does one of these:

  1. takes no input to print/return/generate a list of non-Hamming numbers infinitely, or
  2. takes a positive integer \$n\$ as input to print/return/generate \$n\$th non-Hamming number (can be either 0-indexed or 1-indexed), or
  3. takes a positive integer \$n\$ as input to print/return/generate a list of first \$n\$ non-Hamming numbers.

4. takes a positive integer \$n\$ to print/return/generate non-Hamming number until \$n\$ (suggested by @Wasif, can be inclusive or not; i.e. non-Hamming numbers that are either \$<n\$ or \$\leq n\$). abolished by @rak1507.

Example

This example shows how program/function/subroutine that does 3rd task should work:

  • Input: 5
  • Output: 7, 11, 13, 14, 17

Rules

  • I/O method is done by your desired format.
  • If you are answering one of 2nd or 3rd task, you can assume that input is a non-negative integer.
  • No external resources.
  • Standard loopholes apply.
  • If your program/function/subroutine fails to output huge non-Hamming numbers because of overflow (or similar boundary) but is theotically valid, it is acceptable.
  • Shortest code in bytes wins. However, if someone have won entire of this post, you can still try to win among languages and tasks.

P.S.

It's actually A279622.

\$\endgroup\$
10
  • \$\begingroup\$ sandbox was here \$\endgroup\$
    – user100411
    Apr 18 '21 at 22:21
  • 3
    \$\begingroup\$ I'd usually say that a challenge of outputting not-X numbers is too similar to one of outputting X numbers, though here maybe it's justified because the previous challenge has a restrictive time limit and fewer output options. \$\endgroup\$
    – xnor
    Apr 18 '21 at 22:33
  • \$\begingroup\$ Is it allowed to take until what number to print non hamming numbers like take 15 and output 1,7,11,13? \$\endgroup\$
    – wasif
    Apr 19 '21 at 2:53
  • 5
    \$\begingroup\$ @tailsparkrabbitear I disagree with allowing 'numbers up to n' as it goes against normal sequence challenge convention. \$\endgroup\$
    – rak1507
    Apr 19 '21 at 9:48
  • 1
    \$\begingroup\$ @tailsparkrabbitear Although I agree with (and upvoted) rak1507's comment, I nevertheless disagree with changing the rules retrospectively in a way that invalidates existing answers. At the very least, you need to go-through the answers and alert the affected authors that you've invalidated them. \$\endgroup\$ Apr 20 '21 at 9:48

25 Answers 25

6
\$\begingroup\$

JavaScript (V8), 61 bytes

A full program that prints the sequence forever.

for(k=6;x=++k;)[2,3,5].some(g=d=>x%d?x<2:g(d,x/=d))||print(k)

Try it online!

Commented

for(               // infinite loop:
  k = 6;           //   start with k = 6
  x = ++k;         //   increment k and copy it to x
)                  //
  [2, 3, 5]        // list of primes less than 7
  .some(g = d =>   // for each of them:
    x % d ?        //   if d is not a divisor of x:
      x < 2        //     return true if x = 1
    :              //   else:
      g(d, x /= d) //     divide x by d and do a recursive call
  )                // end of some()
  ||               // if true, k is 5-smooth (aka regular, aka Hamming number)
  print(k)         // otherwise, print it

JavaScript (ES6), 65 bytes

Returns the \$n\$th term of the sequence, 1-indexed.

f=(n,k=6)=>n?f(n-[2,3,5].every(g=d=>x%d?x>1:g(d,x/=d),x=++k),k):k

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Jelly, 6 bytes

30*%µƇ

Try it online!

Takes \$n\$ and outputs all non-Hamming numbers \$\le n\$, as allowed by the OP.

Thanks to Delfad0r for suggesting this method in chat!


Jelly, 7 bytes

ÆfṀ>5Ʋ#

Try it online!

-2 bytes thanks to xnor, who noted that \$k\$ is a non-Hamming number if it's smallest largest (thanks ovs, for catching that) prime factor is greater than \$5\$!

Returns the first \$n\$ non-Hamming numbers


How they work

30*%µƇ - Main link. Takes n on the left
    µƇ - Filter the range i ∈ [1, 2, ..., n] on the following:
30*    -   Raise 30 to the power i
   %   -   That is not divisible by i?

ÆfṂ>5Ʋ# - Main link. Takes no arguments
     Ʋ  - Group the previous 4 links into a monad f(k):
Æf      -   Prime factors of k
  Ṁ     -   Maximum
   >5   -   Greater than 5?
      # - Read n from STDIN and count up k = 1, 2, 3, ... until n such k return True under f(k)
\$\endgroup\$
4
  • \$\begingroup\$ Might it be shorter to check whether the smallest prime factor of k is greater than 5? \$\endgroup\$
    – xnor
    Apr 18 '21 at 22:36
  • \$\begingroup\$ @xnor Yep, that does it. Math wins as usual :) \$\endgroup\$ Apr 18 '21 at 22:38
  • 1
    \$\begingroup\$ I think there was a typo in xnor's comment, it should be the largest prime factor. (14 is now missing from your output,) \$\endgroup\$
    – ovs
    Apr 18 '21 at 22:44
  • \$\begingroup\$ @ovs ...yes, can't believe I didn't notice that \$\endgroup\$ Apr 18 '21 at 22:46
3
\$\begingroup\$

05AB1E, 7 6 bytes

-1 thanks to ovs.

∞ʒÓg3›

Try it online!

∞ʒÓg3›  # full program
 ʒ      # all elements of...
∞       # [1, 2, 3, ...]...
 ʒ      # where...
   g    # the length of...
  Ó     # the exponents of the prime factorization of...
        # (implicit) current element in list...
     ›  # is greater than...
    3   # literal
        # implicit output
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 6 bytes using the exponents of the prime factorization. \$\endgroup\$
    – ovs
    Apr 19 '21 at 8:55
  • \$\begingroup\$ @ovs Thank you! \$\endgroup\$
    – Makonede
    Apr 19 '21 at 15:47
3
\$\begingroup\$

J, 25 bytes

(>:[]echo~5<{:@q:)@]^:_&7

Try it online!

YAIOXI

Yet Another Implementation Of xnor's Idea.

  • ^:_&7 Loop forever, starting with 7:
  • ]echo~... Echo the current count if...
  • 5<{:@q: 5 is less than the last {: prime factor q: (they're listed in ascending order). This step is merely a side effect.
  • >:[ Return the increment of the counter and keep looping.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ +1 for the emoticons :) \$\endgroup\$
    – wasif
    Apr 19 '21 at 3:13
  • \$\begingroup\$ can probably be shortened now the challenge author has made the (wrong) decision to allow non hamming numbers up to n \$\endgroup\$
    – rak1507
    Apr 19 '21 at 9:51
  • \$\begingroup\$ sadly i think expressing condition "while result list <= n" or its equivalent would be more bytes than what i use with echo and ^:_. if i only have to express "do this n times" that would be a different story. it looks like "do this n*n times" would probably be safe, though, but then you'd have to pluck the first n at the end.... \$\endgroup\$
    – Jonah
    Apr 19 '21 at 12:24
3
\$\begingroup\$

Vyxal, 8 5 bytes

Huge thanks to @Lyxal for -3 bytes using a filter lambda, so I could beat all!

'ǐG5>

Takes an integer input \$n\$, and outputs all non-hamming numbers \$\le{n}\$ (According to new rule)

Explanation

'         # Filter lambda
 ǐ        # Prime factors of each number
  G       # Maximum
   5>     # Greater than 5?
          # Implicitly output 

Try it!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is the definition of amazing \$\endgroup\$
    – lyxal
    Apr 19 '21 at 8:27
2
\$\begingroup\$

Husk, 7 bytes

Uses xnor's idea.

foV>5pN

Try it online!

Outputs an infinite list.

foV>5pN
      N  From the infinite list of natural numbers,
f        keep the ones that satisfy the following predicate
  V      There exists
     p   a prime factors
   >5    that is greater than 5
\$\endgroup\$
3
  • \$\begingroup\$ Crap, beat me to it, was literally about to post fȯ>5▼pN \$\endgroup\$
    – rak1507
    Apr 18 '21 at 22:51
  • \$\begingroup\$ @rak1507 You can still post it, it's a bit different. \$\endgroup\$
    – user
    Apr 18 '21 at 22:52
  • \$\begingroup\$ just realised it's wrong anyway :P oh well \$\endgroup\$
    – rak1507
    Apr 18 '21 at 22:57
2
\$\begingroup\$

Factor + lists.lazy math.primes.factors math.unicode, 51 bytes

1 lfrom [ factors [ 5 > ] ∃ ] lfilter [ . ] leach

Try it online!

Explanation:

It's a full program that prints non-Hamming numbers forever, using @xnor's tip about prime factors greater than 5.

  • 1 lfrom An infinite lazy list of the natural numbers.
  • [ factors [ 5 > ] ∃ ] lfilter Select numbers with a prime factor greater than 5. is shorthand for any? and this turns out to be 1 byte shorter than supremum 5 >.
  • [ . ] leach Print every item in the list.
\$\endgroup\$
2
\$\begingroup\$

Haskell, 25 bytes

[n|n<-[1..],mod(30^n)n>0]

Try it online!

The infinite list of non-Hamming numbers.

How?

A positive integer \$n\$ is Hamming if and only if \$n\$ divides \$30^n\$.

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

JavaScript (Browser), 31 bytes

for(k=1n;;)30n**++k%k&&alert(k)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ +1, You are always beating Arnauld :-) \$\endgroup\$
    – wasif
    Apr 19 '21 at 9:01
  • \$\begingroup\$ @Wasif Maybe due to the fact that Arnauld is more active than me on PPCG. As a result, Arnauld often posts answer before I ever checked the question. And I will not post my answer if it is not quite interesting (longer than existed answers). \$\endgroup\$
    – tsh
    Apr 19 '21 at 9:18
2
\$\begingroup\$

R, 69 70 69 67 bytes

while(T<-T+1)for(i in 1:T+6)if(sum(!i%%2:i)<2&!T%%i){show(T);break}

Try it online!

xnor's idea in base R.

+1 thanks to @Dominic spotting an error and then -1 golfing print to show.

\$\endgroup\$
5
  • \$\begingroup\$ Er, I think you're correct to be suspicious of the next: try it without next... \$\endgroup\$ Apr 19 '21 at 7:58
  • 1
    \$\begingroup\$ (but I think that the problem is that next isn't doing what you want: you're getting 77 twice, for instance...) \$\endgroup\$ Apr 19 '21 at 8:15
  • \$\begingroup\$ A horrible fix for +8 bytes \$\endgroup\$ Apr 19 '21 at 8:21
  • \$\begingroup\$ @DominicvanEssen thanks for spotting the 77 error - I think break should do the trick for +1: Try it online!. But I still don't like it :( \$\endgroup\$
    – pajonk
    Apr 19 '21 at 8:26
  • 1
    \$\begingroup\$ Looks good now, and you can have your byte back... \$\endgroup\$ Apr 19 '21 at 8:42
1
\$\begingroup\$

Retina, 44 bytes

K`
"$+"{`$
_
)+`^((_+)(?=\2{1,4}$))*_$
$&_
_

Try it online! Outputs the nth number. No test suite because of the way the program uses history. Explanation:

K`

Delete the input, replacing it with unary 0.

"$+"{`
)`

Repeat the input number of times.

$
_

Increment the current value.

+`^((_+)(?=\2{1,4}$))*_$

While the current value is a product of powers of 2, 3, 4 or 5...

$&_

... increment it.

_

Convert the result to decimal.

To convert the script into one that outputs the first n numbers:

  • Remove the ) at the beginning of the 4th line
  • Prefix .*\` to the last line.
\$\endgroup\$
1
\$\begingroup\$

Pyth, 14 12 bytes

7W=hTI<5ePTT

Try it online!

Prints the infinite sequence.

7     # First print 7 separately.
W     # While
T     # Initialized to 10 by default
=hT   # Increment T by 1
PT    # Lists prime factors of T in increasing order.
>ePT5 # If the highest prime factor is greater than 5, then
T     # Print T

-2 bytes thanks to kops

\$\endgroup\$
1
  • \$\begingroup\$ 12 bytes \$\endgroup\$
    – kops
    Apr 19 '21 at 10:00
1
\$\begingroup\$

Stax, 7 bytes

üu§└ÿà♦

Run and debug it

TIL that |M returns infinity for empty lists. Found a method without |M.

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

PowerShell Core, 56 bytes

inspired by Julian's answer (loop instead recursion)

1.."$args"|?{$a=$_;2,3,5|%{for(;!($a%$_)){$a/=$_}};$a-1}

Try it online!

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

Ruby, 26 bytes

1.step{|x|30**x%x>0&&p(x)}

Try it online!

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

Japt, 9 bytes

Outputs the first n terms.

Èk d¨7}jU

Try it

Èk d¨7}jU     :Implicit input of integer U
È             :Function taking an integer as input
 k            :  Prime factors
   d          :  Any?
    ¨7        :    Greater than equal to 7
      }       :End function
       jU     :Get the first U integers that return true
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 23 bytes

≔⁰θFN«≦⊕θW¬﹪X³⁰θθ≦⊕θ⟦Iθ

Try it online! Link is to verbose version of code. Outputs the first n numbers. Explanation: Uses @Delfad0r's approach.

≔⁰θ

Start at zero.

FN«

Repeat n times.

≦⊕θ

Increment the accumulator.

W¬﹪X³⁰θθ

While it divides its power of 30...

≦⊕θ

... increment it.

⟦Iθ

Output the found value on its own line.

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

R + gmp, 37 51 bytes

Edit: +14 bytes after the rules were changed to disallow outputting all non-Hamming numbers up to n: now outputs the infinite list

n=gmp::as.bigz(1);repeat if(60^(n=n+1)%%n>0)show(n)

Try it online!

Outputs infinite list of non-Hamming numbers.

Uses arbitrary-precision calculations to simply check whether n divides the nth power of 60 (this is sufficient to be certain that it also can't divide any higher power of 60). We could have stopped at the floor(log2(n))th power of 60, but it would have made an annoyingly long program.

Of course, the mathematics itself is correct even without the gmp library to handle the actual abritrary-precision calculations... so we could have an even shorter version in base-R if we don't mind going out-of-range for "huge" non-Hamming numbers:


R, 35 44 bytes

Edit: +9 bytes to comply with the changed rules

repeat if(30^(log2(T<-T+1)%/%1)%%T>0)show(T)

Try it online!

Same approach as above, but goes out-of-range for "huge" non-Hamming numbers, defined as any number greater than 16383.

If we are somewhat more timid and define a "huge" to be any number greater than 12 (and accept that above this the program will output junk or crash), then we can have an even shorter 23-byte 34-byte solution of just repeat if(30^(T<-T+1)%%T>0)show(T) Try it!.

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

Pari/GP, 66 bytes

It was easier to generate many (seven) times as many numbers as needed, then trim the excess:

h(n)=select(x->factor(x)[,1][-1..-1][1]>5,vector(7*n,i,i+1))[1..n]

Try it online!

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

Pari/GP, 56 bytes

Generates an infinite sequence of non-Hamming numbers

i=7;while(1,if(factor(i)[,1][-1..-1][1]>5,print(i));i++)

Try it online!

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

PowerShell Core, 137 89 bytes

filter d{param($b)if($_%$b){$_}else{$_/$b|d $b}}1.."$args"|d 3|d 5|d 2|?{++$t;$_-1}|%{$t}

Try it online!

Thanks mazzy!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ nice. you can save some bytes with filter Try it online! \$\endgroup\$
    – mazzy
    Apr 19 '21 at 8:37
  • 1
    \$\begingroup\$ ...and some bytes more Try it online! \$\endgroup\$
    – mazzy
    Apr 19 '21 at 8:52
  • 1
    \$\begingroup\$ I don't understand why you check the $u for zero Try it online! \$\endgroup\$
    – mazzy
    Apr 19 '21 at 9:05
  • 1
    \$\begingroup\$ ...and final Try it online! \$\endgroup\$
    – mazzy
    Apr 19 '21 at 10:45
  • 1
    \$\begingroup\$ ok, my bad, I didn't see the or between all the rules and tried to make work the no parameter and the give n numbers out, and probably some good golfing you did ! I didn't know you could pass parameters to filters! \$\endgroup\$
    – Julian
    Apr 19 '21 at 21:37
1
\$\begingroup\$

Zsh, 44 43 bytes

seq inf|factor|grep ' 7
 .[^ ]'|cut -d: -f1

Try it online!

-1 thanks to @tail spark rabbit ear

  • seq inf: count up infinitely
  • factorise each number in the form 52: 2 2 13
  • grep: keep only lines matching the regular expression 7\n .[^ ]
    • The newline acts like "or"
    • Essentially matches either a factor that starts with 7, or a factor with more than one digit. This will match any prime > 5, so as long as there's at least one matching factor, the whole line will be printed
  • cut -d: -f1: take the first field (where fields are separated by colons) of each line. This gets only the number itself

Zsh, 45 bytes

for ((;++a;)){>`factor $a`;><7->&&<<<$a;rm *}

Try it online!

  • for ((;++a;)){}: for each integer up to infinity:
    • factor $a: factorise the number in the form 52: 2 2 13
    • >``: create the files according to the words in the factorisation (e.g. 52:, 2 (duplicates are just ignored), and 13)
    • <7->: look for a file which is a number greater than or equal to 7
      • If the number has a prime factor greater than 5, it is not a Hamming number and will be matched
      • The number itself always has a trailing colon, so it can never be matched by this
    • >: and try to output to it
    • &&: if that works, then:
      • <<<$a: print the number
    • rm *: remove all the files (so we're fresh for the next iteration)
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 43 bytes: no ERE needed in this case because separating BREs with LFs stands for | in ERE when greping. \$\endgroup\$
    – user100411
    May 7 '21 at 14:03
0
\$\begingroup\$

PowerShell, 235 bytes

param($k)$s='$f;$n/=$f';function F($n){$m=[math]::sqrt($n);$f=2;while(!($n%$f)){iex $s};$f=3;while($f-le$m-and$n-ge$m){while(!($n%$f)){iex $s};$f+=2};$n};$a=@();$a=@();$g=1;while($a.length-lt$k){$j=(F($g)[-1])-gt5;if($j){$a+=$g}$g++}$a

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Julia 0.4, 52 bytes

x=1;while x>0 keys(factor(x+=1))⊆1:5||print(-x)end

Try it online!

I'm using Julia 0.4 for factor, which was then moved in the package Primes.jl

also works with recent versions of Julia + Primes.jl

factor(x) returns a Dict with the keys been the prime factors and the values the exponent of each factor

in more recent version with Primes.jl, factor(Set,x) can be called instead for the same result

\$\endgroup\$
0
\$\begingroup\$

AWK, 92 bytes

Previously 93 bytes that outputs intfinite list.

Given a line of an integer \$n\$, outputs first \$n\$ nunbers.

Pretty naïve.

{for(k=j=7;$0--;k=++j){for(;k%2-1;k/=2);for(;!(k%3);k/=3);for(;!(k%5);k/=5);if(k>1)print j}}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ FYI inversing the conditions on this program does not pass the original task because of time limitation. \$\endgroup\$
    – user100411
    Apr 24 '21 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy